1496. Path Crossing

Задача

Дана строка перемещений N/S/E/W от точки (0,0). Верните true, если путь пересекает сам себя.

Примеры

Пример 1

Input: path = "NES"
Output: false

Пояснение

Путь не проходит ни через одну точку дважды.

Пример 2

Input: path = "NESWW"
Output: true

Пояснение

Путь дважды посещает начало координат.

Решение

Решение

// Time Complexity:  O(n)
// Space Complexity: O(n)
var isPathCrossing = function(path) {
    const movements = {
        N: [0, 1],
        S: [0, -1],
        W: [-1, 0],
        E: [1, 0]
    };
 
    let x = 0,
        y = 0;
    const visited = new Set(['0#0']);
 
    for (const dir of path) {
        x += movements[dir][0];
        y += movements[dir][1];
 
        const key = `${x}#${y}`;
        if (visited.has(key)) return true;
        visited.add(key);
    }
 
    return false;
};

Решение 2

// Time Complexity:  O(n)
// Space Complexity: O(n)
var isPathCrossing = function (path) {
    let x = 0, y = 0;
    const visited = new Set(['0#0']);
 
    for (const dir of path) {
        if (dir === 'N') y++;
        else if (dir === 'S') y--;
        else if (dir === 'E') x++;
        else x--;
 
        const key = `${x}#${y}`;
        if (visited.has(key)) return true;
        visited.add(key);
    }
 
    return false;
};