1496. Path Crossing

LeetCode easy original: C# #backtracking #csharp #easy #hash-table #leetcode #string

Task text is translated from Russian for the selected interface language. Code is left unchanged.

LeetCode Static

Дана string path, где path[i] = 'N', 'S', 'E' или 'W', каждая из которых представляет движение на одну единицу на север, юг, восток или запад соответственно. Вы начинаете с точки (0, 0) на 2D плоскости и идете по пути, указанному в path.

return true, если путь пересекает сам себя в какой-либо точке, то есть если вы в какой-то момент окажетесь в месте, которое уже посещали ранее. В противном случае return false.

Example:

Input: path = "NESWW"

Output: true

Explanation: Notice that the path visits the origin twice.

C# solution

matched/original

public class Solution {
    public bool IsPathCrossing(string path) {
        var moves = new Dictionary<char, (int, int)> {
            {'N', (0, 1)}, {'S', (0, -1)}, {'E', (1, 0)}, {'W', (-1, 0)}
        };
        var visited = new HashSet<(int, int)> { (0, 0) };
        int x = 0, y = 0;
        foreach (char c in path) {
            var move = moves[c];
            x += move.Item1;
            y += move.Item2;
            if (visited.Contains((x, y))) {
                return true;
            }
            visited.Add((x, y));
        }
        return false;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool IsPathCrossing(string path) {
        var moves = new unordered_map<char, (int, int)> {
            {'N', (0, 1)}, {'S', (0, -1)}, {'E', (1, 0)}, {'W', (-1, 0)}
        };
        var visited = new HashSet<(int, int)> { (0, 0) };
        int x = 0, y = 0;
        foreach (char c in path) {
            var move = moves[c];
            x += move.Item1;
            y += move.Item2;
            if (visited.Contains((x, y))) {
                return true;
            }
            visited.push_back((x, y));
        }
        return false;
    }
}

Java solution

matched/original

class Solution {
    public boolean isPathCrossing(String path) {
        Map<Character, Pair<Integer, Integer>> moves = new HashMap();
        moves.put('N', new Pair(0, 1));
        moves.put('S', new Pair(0, -1));
        moves.put('W', new Pair(-1, 0));
        moves.put('E', new Pair(1, 0));
        
        Set<Pair<Integer, Integer>> visited = new HashSet();
        visited.add(new Pair(0, 0));
        
        int x = 0;
        int y = 0;
        
        for (Character c : path.toCharArray()) {
            Pair<Integer, Integer> curr = moves.get(c);
            int dx = curr.getKey();
            int dy = curr.getValue();
            x += dx;
            y += dy;
            
            Pair<Integer, Integer> pair = new Pair(x, y);
            if (visited.contains(pair)) {
                return true;
            }
            
            visited.add(pair);
        }
        
        return false;
    }
}

JavaScript solution

matched/original

var isPathCrossing = function(path) {
    const moves = {
        'N': [0, 1], 'S': [0, -1],
        'E': [1, 0], 'W': [-1, 0]
    };
    const visited = new Set(['0,0']);
    let x = 0, y = 0;

    for (const c of path) {
        const [dx, dy] = moves[c];
        x += dx;
        y += dy;
        const point = `${x},${y}`;
        if (visited.has(point)) {
            return true;
        }
        visited.add(point);
    }

    return false;
};

Python solution

matched/original

class Solution:
    def isPathCrossing(self, path: str) -> bool:
        moves = {'N': (0, 1), 'S': (0, -1), 'E': (1, 0), 'W': (-1, 0)}
        visited = {(0, 0)}
        x = 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

Algorithm

1⃣Инициализация переменных:

Создать хэш-карту moves, которая сопоставляет символы 'N', 'S', 'E', 'W' с соответствующими значениями.

Инициализировать множество visited с начальной точкой (0, 0).

Установить начальные координаты x = 0 и y = 0.

2⃣Проход по строке path:

Для каждого символа c в path получить значения (dx, dy) из moves[c].

Обновить координаты: добавить dx к x и dy к y.

Проверить, содержится ли текущая точка (x, y) в visited. Если да, вернуть true.

Добавить текущую точку (x, y) в visited.

3⃣Возврат результата:

Если ни одна точка не пересекалась, вернуть false.

😎

Vacancies for this task

Active vacancies with overlapping task tags are shown.

All vacancies

There are no active vacancies yet.