⚡Flashcard Drill➔
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

  1. Simulate the walk, recording every visited coordinate in a hash set.
  2. Before moving to a new coordinate, check whether it is already in the set. If so, the path crosses itself.
  3. The set must include the starting point (0, 0) so that returning to the origin is detected as a crossing.
  4. 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 x and y are 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.
🎯 Drill This Card Now➔

🧩 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