---
# System prepended metadata

title: 1496. Path Crossing

---

Daily 23/12/2023: [1496. Path Crossing](https://leetcode.com/problems/path-crossing/)

# 1. Tóm tắt đề bài
Cho một chuỗi ```path```, trong đó ```path[i] = 'N', 'S', 'E'hoặc 'W'```, mỗi chuỗi đại diện cho việc di chuyển một đơn vị tương ứng về phía bắc, nam, đông hoặc tây. Bạn bắt đầu từ điểm gốc ```(0, 0)``` trên mặt phẳng 2D và đi trên con đường được chỉ định bởi ```path```.

Trả lại ```true``` nếu đường dẫn đi qua chính nó tại bất kỳ điểm nào, tức là nếu bất kỳ lúc nào bạn đang ở vị trí mà bạn đã ghé thăm trước đó. Nếu không trả về ```false```.
 
#### Giới hạn
- $-1 \le$ ```path.length``` $\le 10^4$

# 2. Tóm tắt lời giải

#### Phân tích
- Với bài này thực chất chỉ là kiểm tra khả năng ```if else``` mà thôi.
- Với mỗi hướng bạn cộng tọa độ phù hợp, hoặc có thể dùng ```map``` để lưu các tọa độ cộng.
# 3. Lời giải chi tiết
#### Code
```python
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
```
#### Độ phức tạp
$O(n)$
# 4. Kết luận & gợi ý mở rộng
- Đây là một bài luyện tâp cấu trúc dữ liệu dạng ```Hash Table```
> Hãy dùng nghị lực và sự kiên trì để đánh bại mọi thứ.

###### #Hashtag: <span style='color: blue'>Hash Table, String</span>