NeetCode #76LC-1496EasyArrays & Hashing
← Back to All Problems#76 · #1496 · Path Crossing(判断路径是否相交)
📌 Problem Statement & Constraints
Given a string
path where each segment is 'N', 'S', 'E' or 'W', starting at the origin, determine whether the path crosses itself at any point. Constraints: 1 <= path.length <= 10^4.💡 Core Algorithmic Approaches
- Simulate the walk, recording every visited coordinate in a hash set.
- Before moving to a new coordinate, check whether it is already in the set. If so, the path crosses itself.
- The set must include the starting point
(0, 0)so that returning to the origin is detected as a crossing. - Each step is O(1), so the whole simulation is linear.
💻 Benchmark Python3 Implementation
class Solution:
def isPathCrossing(self, path: str) -> bool:
x = y = 0
seen = {(0, 0)} # the start counts as visited
move = {"N": (0, 1), "S": (0, -1), "E": (1, 0), "W": (-1, 0)}
for ch in path:
dx, dy = move[ch]
x += dx
y += dy
if (x, y) in seen:
return True # revisited -> crossing
seen.add((x, y))
return False⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one step per character with O(1) hash operations.
💾 Space Complexity
O(n) for the visited set.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting to seed the set with
(0, 0): a path returning to the origin would not be flagged, e.g."NESW". - Using a list of visited points: membership becomes O(n), giving O(n^2) overall.
- Checking before moving instead of after: the crossing is detected at the destination cell, so the test must happen after the update.
- Storing only one coordinate: both
xandyare needed to identify a cell.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Arrays & Hashing Problems
中文速览与面试要点
判断路径是否相交
给你一个字符串 path,其中 path[i] 的值可以是 N、S、E 或 W,分别表示向北、向南、向东、向西移动一个单位。机器人从二维平面上的原点 (0, 0) 处开始出发,按 path 所指示的路径行走。如果路径在任何位置 相交 (即在同一个点经过两次或以上),返回 true;否则返回 false。注意:起点 (0, 0) 也算作已经过点。约束:1 ≤ path.length ≤ 10^4;path[i] 为 N、S、E 或 W 之一。
核心要点
- 哈希集合记录访问过的坐标(标准解) :用集合保存所有经过的坐标点,初始包含起点 (0, 0)。每移动一步,若新坐标已在集合中则返回 True,否则加入集合。
- 为什么起点要预先放入 :题目明确起点也算已经过点,因此若路径绕回原点也算相交。
- 坐标更新 :N 令 y 加一,S 令 y 减一,E 令 x 加一,W 令 x 减一。
- 复杂度 :n 步移动,每步集合操作均摊 O(1),总计 O(n)。
常见陷阱
- 忘记把起点放入集合 :会导致「绕回原点」被漏检。题目明确起点算已经过点。
- 先加入集合再判断 : seen.add((x,y)) 后再 if (x,y) in seen 恒为 True,逻辑完全错误。必须 先判断、后加入 。
- 方向映射写错 :N/S 影响 y,E/W 影响 x。把 N 映射到 x 轴会导致结果错误。
- 用字符串编码坐标 :如 f"x,y" ,可行但比元组稍慢;元组可直接哈希,更简洁。
参考实现
class Solution:
def isPathCrossing(self, path: str) -> bool:
x = y = 0
seen = {(0, 0)} # 起点也算已经过点
delta = {'N': (0, 1), 'S': (0, -1), 'E': (1, 0), 'W': (-1, 0)}
for d in path:
dx, dy = delta[d]
x += dx
y += dy
if (x, y) in seen:
return True
seen.add((x, y))
return False