Problem 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.
Key Insights
- The path can be visualized as a series of movements on a 2D grid.
- We need to check if any position is visited more than once.
- A hash table (set) can be used to track visited coordinates efficiently.
- The movement directions correspond to changes in x or y coordinates.
Space and Time Complexity
Time Complexity: O(n) - where n is the length of the path string, as we traverse the string once. Space Complexity: O(n) - in the worst case, we store every position in the hash set.
Solution
To solve the problem, we can utilize a hash set to keep track of each coordinate the path visits. Starting at the origin (0, 0), we will iterate through each character in the string. For each character, we will update our current position based on the direction indicated ('N', 'S', 'E', 'W'). After updating the position, we will check if it's already in the hash set. If it is, we return true since the path crosses itself. If we finish iterating through the path without finding a repeat position, we return false.