Sponsored
Sponsored
The idea is to use a Set (or a HashSet in some languages) to store each coordinate visited during the path traversal. Starting from (0, 0), each movement updates the coordinates. If the updated coordinates are already in the Set, it means that the path has crossed itself, and we return true. Otherwise, continue until the end of the path and return false.
Time Complexity: O(n), where n is the length of the path, as we iterate through the path once, with O(1) operations for each set lookup.
Space Complexity: O(n), as we store up to n coordinates in the set.
1def isPathCrossing(path):
2 visited = set()
3 x, y = 0, 0
4 visited.add((x, y))
5
6 for direction in path:
7 if direction == 'N':
8 y += 1
9 elif direction == 'S':
10 y -= 1
11 elif direction == 'E':
12 x += 1
13 elif direction == 'W':
14 x -= 1
15
16 if (x, y) in visited:
17 return True
18 visited.add((x, y))
19
20 return FalseThis Python solution initializes a set for visited coordinates, and starts at the origin (0, 0). It then iterates over the path, updating the x and y coordinates based on the direction. The coordinate (x, y) is checked against the set to see if it already exists. If it does, the path has crossed itself, and the function returns True. Otherwise, it continues until the end, returning False.
In this approach, we simulate movement on a 2D plane. Starting at the origin (0, 0), the path string is processed character by character to update the current position based on the direction: 'N' increases y, 'S' decreases y, 'E' increases x, and 'W' decreases x. A map or set records visits to each unique position. If a position is visited more than once, the path crosses itself.
Time Complexity: O(n), since every character in the path is processed.
Space Complexity: O(n), as we store coordinates in a set.
1#include <unordered_set>
2#include <utility>
class Solution {
public:
bool isPathCrossing(string path) {
std::unordered_set<std::pair<int,int>, pair_hash> visited;
int x = 0, y = 0;
visited.insert({x, y});
for (char direction : path) {
if (direction == 'N') {
++y;
} else if (direction == 'S') {
--y;
} else if (direction == 'E') {
++x;
} else if (direction == 'W') {
--x;
}
if (visited.count({x, y})) {
return true;
}
visited.insert({x, y});
}
return false;
}
private:
struct pair_hash {
template <class T1, class T2>
std::size_t operator () (const std::pair<T1, T2>& pair) const {
auto hash1 = std::hash<T1>{}(pair.first);
auto hash2 = std::hash<T2>{}(pair.second);
return hash1 ^ hash2;
}
};
};This C++ implementation uses unordered_set to store pairs representing each visited point. Starting at the origin, the code adjusts x and y based on direction, checks for revisited points, and updates the set.