Skip to content

1619. Path Crossing

Hash Table String

Problem - Path Crossing

Easy

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.

 

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 <= 104
  • path[i] is either 'N', 'S', 'E', or 'W'.

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def isPathCrossing(self, path: str) -> bool:
        coordinates = [[0,0]]

        for ch in path:
            c = list(coordinates[-1])
            if ch=='N':
                c[0] += 1

            elif ch=='S':
                c[0] -= 1

            elif ch=='E':
                c[1] += 1

            else:
                c[1] -= 1

            if c in coordinates:
                return True

            coordinates.append(c)
        return False

Submission Stats:

  • Runtime: 35 ms (4.23%)
  • Memory: 17.4 MB (100.00%)