Path Crossing

The problem requires you to determine if a given path crosses itself at any point. To solve this problem, we need to keep track of all the points we have visited on the path and check if we ever visit a point we have already been to.

We can represent each point on the path by a pair of coordinates (x, y). We start at the origin (0, 0). Then, for each character in the input string, we adjust our current coordinates accordingly:

• If the character is ‘N’, we increase our y-coordinate by 1 (moving north).
• If the character is ‘S’, we decrease our y-coordinate by 1 (moving south).
• If the character is ‘E’, we increase our x-coordinate by 1 (moving east).
• If the character is ‘W’, we decrease our x-coordinate by 1 (moving west).

After moving, we check if the new point is already in the set of visited points. If it is, the path crosses itself, and we return true. If it isn’t, we add the new point to the set and continue with the next character in the string. If we finish going through the string without finding a crossing, we return false.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def isPathCrossing(self, path: str) -> bool:
        x, y = 0, 0  # Starting point
        visited = set([(x, y)])  # We start at the origin

        # Dictionary to map directions to coordinate changes
        directions = {'N': (0, 1), 'S': (0, -1), 'E': (1, 0), 'W': (-1, 0)}

        for move in path:
            dx, dy = directions[move]  # Get the coordinate change for this move
            x, y = x + dx, y + dy  # Update coordinates
            if (x, y) in visited:  # If we have visited this point before, the path crosses itself
                return True
            visited.add((x, y))  # Add the new point to the set of visited points

        # If we have gone through the entire path without finding a crossing, return False
        return False

This solution works for all valid input strings and has a time complexity of O(n), where n is the length of the string.