LeetCode 1496: Path Crossing

Explanation

To solve this problem, we can keep track of the visited points in a set. We start at the origin (0,0) and iterate over each direction specified in the path. For each direction, we move one unit in that direction and add the current point to the set of visited points. If at any point, we reach a point that is already in the set, we return true indicating that the path crosses itself. If we complete the path traversal without crossing ourselves, we return false.

• Time complexity: O(n) where n is the length of the path string
• Space complexity: O(n) to store the visited points

class Solution {
    public boolean isPathCrossing(String path) {
        Set<String> visited = new HashSet<>();
        visited.add("0,0");
        int x = 0, y = 0;
        
        for(char direction : path.toCharArray()) {
            if(direction == 'N') y++;
            else if(direction == 'S') y--;
            else if(direction == 'E') x++;
            else if(direction == 'W') x--;
            
            String point = x + "," + y;
            if(visited.contains(point)) return true;
            visited.add(point);
        }
        
        return false;
    }
}