LeetCode 1496. Path Crossing

Description

https://leetcode.com/problems/path-crossing/

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’ve previously visited. Return False otherwise.

Example 1:

Input: path = "NES"
Output: false 
Explanation: Notice that the path doesn't cross any point more than once.

Example 2:

Input: path = "NESWW"
Output: true
Explanation: Notice that the path visits the origin twice.

Constraints:

• 1 <= path.length <= 10^4
• path will only consist of characters in {'N', 'S', 'E', 'W}

Explanation

Track the position visited and check if any position revisited.

Python Solution

class Solution:
    def isPathCrossing(self, path: str) -> bool:
        directions = {
            'N': [0, 1],
            'S': [0, -1],
            'E': [1, 0],
            'W': [-1, 0]            
        }
        
        
        
        visited = defaultdict(set)   
        position = [0, 0]
        visited[position[0]].add(position[1])
            
        for c in path:
            d = directions[c]
            
            position = [position[0] + d[0], position[1] + d[1]]
            
            
            if position[0] in visited and position[1] in visited[position[0]]:
                return True
            
            visited[position[0]].add(position[1])
            
        return False