Problem of The Day: Cross Pathing

Problem Statement

leetcode problem link

Brute Force [Accepted]

class Solution:
    def isPathCrossing(self, path: str) -> bool:
        seen = set()
        seen.add((0,0))
        directions = {
            'N': 1,
            'E': 1,
            'S': -1,
            'W': -1
        }
        coords = [0,0]
        for d in path:
            new_coord = coords[:]
            if d in 'NS':
                new_coord[0] += directions[d]
            if d in 'WE':
                new_coord[1] += directions[d]
            if tuple(new_coord) in seen:
                return True
            seen.add(tuple(new_coord))
            coords = new_coord[:]
        return False

Editorial

Approach: Hash Set

class Solution:
    def isPathCrossing(self, path: str) -> bool:
        moves = {
            "N": (0, 1),
            "S": (0, -1),
            "W": (-1, 0),
            "E": (1, 0)
        }

        visited = {(0, 0)}
        x = 0
        y = 0

        for c in path:
            dx, dy = moves[c]
            x += dx
            y += dy

            if (x, y) in visited:
                return True

            visited.add((x, y))

        return False