Determine whether a walk on the integer grid ever revisits a point.
Path Crossing
You start at the origin on an infinite 2D integer grid. A route is given as a string of moves, where each character represents one step:
N: move up by 1S: move down by 1E: move right by 1W: move left by 1
Your task is to determine whether the path ever crosses itself, meaning that some coordinate is visited more than once, including the starting point.
Return true if any position is visited at least twice; otherwise return false.
Input Format
- A single string
pathcontaining only the charactersN,S,E, andW.
Output Format
- Return a boolean value indicating whether the path crosses itself.
Constraints
1 <= path.length <= $10^{4}$- Each character of
pathis one of{N, S, E, W}
Hints
- Track every coordinate you have visited so far.
- After each move, check whether the new coordinate has appeared before.
- A hash set is a natural fit for storing visited points efficiently.
Input Format
path: a string of moves usingN,S,E,W.
Output Format
trueif the route visits any coordinate more than once; otherwisefalse.
Constraints
1 <= path.length <= $10^{4}$path[i] ∈ {N, S, E, W}
Example 1
Input
path = "NES"
Output
false
Explanation
The path visits (0,0) -> (0,1) -> (1,1) -> (1,0). No coordinate is visited twice.
Example 2
Input
path = "NESWW"
Output
true
Explanation
The path visits (0,0) -> (0,1) -> (1,1) -> (1,0) -> (0,0) -> (-1,0). The origin is visited again, so the path crosses itself.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.