Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1496.html
1496. Path Crossing (Easy)
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've 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 <= 10^4
path
will only consist of characters in{'N', 'S', 'E', 'W}
Related Topics:
String
Solution 1.
-
class Solution { public boolean isPathCrossing(String path) { char[] directionChars = {'N', 'S', 'E', 'W'}; int[][] directions = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} }; Map<Character, Integer> map = new HashMap<Character, Integer>(); for (int i = 0; i < 4; i++) map.put(directionChars[i], i); Set<String> set = new HashSet<String>(); int x = 0, y = 0; set.add(Arrays.toString(new int[]{0, 0})); int length = path.length(); for (int i = 0; i < length; i++) { char c = path.charAt(i); int index = map.get(c); int[] direction = directions[index]; x += direction[0]; y += direction[1]; int[] array = {x, y}; if (!set.add(Arrays.toString(array))) return true; } return false; } } ############ 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; } }
-
// OJ: https://leetcode.com/problems/path-crossing/ // Time: O(N) // Space: O(N) class Solution { long hash(int x, int y) { return (long)x * 10000 + y; } public: bool isPathCrossing(string path) { unordered_set<long> s; int x = 0, y = 0; s.insert(hash(x, y)); for (char c : path) { if (c == 'N') ++y; else if (c == 'E') ++x; else if (c == 'S') --y; else --x; long key = hash(x, y); if (s.count(key)) return true; s.insert(key); } return false; } };
-
class Solution: def isPathCrossing(self, path: str) -> bool: x = y = 0 vis = {(x, y)} for c in path: if c == 'N': y += 1 elif c == 'S': y -= 1 elif c == 'E': x += 1 else: x -= 1 if (x, y) in vis: return True vis.add((x, y)) return False
-
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 }
-
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; }