Description
Given a string path, where path[i] = 'N', 'S', 'E' or 'W', each representing moving one unit north, south, east, or west, respectively. You start at the origin (0, 0) on a 2D plane and walk on the path specified by path.
Return true if the path crosses itself at any point, that is, if at any time you are on a location you have previously visited. Return false otherwise.
Example 1:
Input: path = "NES"
Output: false
Explanation: Notice that the path doesn't cross any point more than once.
Example 2:
Input: path = "NESWW"
Output: true
Explanation: Notice that the path visits the origin twice.
Constraints:
1 <= path.length <= 104path[i] is either 'N', 'S', 'E', or 'W'.
Solutions
Solution 1
PythonJavaC++GoTypeScript
class Solution:
def isPathCrossing(self, path: str) -> bool:
i = j = 0
vis = {(0, 0)}
for c in path:
match c:
case 'N':
i -= 1
case 'S':
i += 1
case 'E':
j += 1
case 'W':
j -= 1
if (i, j) in vis:
return True
vis.add((i, j))
return False(code-box)
class Solution {
public boolean isPathCrossing(String path) {
int i = 0, j = 0;
Set<Integer> vis = new HashSet<>();
vis.add(0);
for (int k = 0, n = path.length(); k < n; ++k) {
switch (path.charAt(k)) {
case 'N' -> --i;
case 'S' -> ++i;
case 'E' -> ++j;
case 'W' -> --j;
}
int t = i * 20000 + j;
if (!vis.add(t)) {
return true;
}
}
return false;
}
}(code-box)
class Solution {
public:
bool isPathCrossing(string path) {
int i = 0, j = 0;
unordered_set<int> s{{0}};
for (char& c : path) {
if (c == 'N') {
--i;
} else if (c == 'S') {
++i;
} else if (c == 'E') {
++j;
} else {
--j;
}
int t = i * 20000 + j;
if (s.count(t)) {
return true;
}
s.insert(t);
}
return false;
}
};(code-box)
func isPathCrossing(path string) bool {
i, j := 0, 0
vis := map[int]bool{0: true}
for _, c := range path {
switch c {
case 'N':
i--
case 'S':
i++
case 'E':
j++
case 'W':
j--
}
if vis[i*20000+j] {
return true
}
vis[i*20000+j] = true
}
return false
}(code-box)
function isPathCrossing(path: string): boolean {
let [i, j] = [0, 0];
const vis: Set<number> = new Set();
vis.add(0);
for (const c of path) {
if (c === 'N') {
--i;
} else if (c === 'S') {
++i;
} else if (c === 'E') {
++j;
} else if (c === 'W') {
--j;
}
const t = i * 20000 + j;
if (vis.has(t)) {
return true;
}
vis.add(t);
}
return false;
}(code-box)
