What is the time complexity of the Path Crossing problem?

The time complexity is O(n), where n is the length of the path, as we visit each location once and check for revisits in constant time using a hash table.

What is the space complexity of the Path Crossing problem?

The space complexity is O(n), due to the need to store the visited points in a hash table.

How can I optimize the Path Crossing solution?

Using a hash table to store visited points ensures that the solution is both time and space efficient, with constant-time lookups and updates.

What are common mistakes when solving the Path Crossing problem?

Common mistakes include forgetting to track the starting point or using inefficient data structures like arrays for storing visited points.

What is the key pattern to solving the Path Crossing problem?

The key pattern is to simulate the path while tracking visited points using a hash table to efficiently check for path crossings.

#1496

Easy

auto_awesome哈希·表·结合·string

LeetCode 题解工作台

判断路径是否相交

给你一个字符串 path ，其中 path[i] 的值可以是 'N' 、 'S' 、 'E' 或者 'W' ，分别表示向北、向南、向东、向西移动一个单位。你从二维平面上的原点 (0, 0) 处开始出发，按 path 所指示的路径行走。如果路径在任何位置上与自身相交，也就是走到之前已经走过的位置，…

哈希表字符串

题目描述

给你一个字符串 path，其中 path[i] 的值可以是 'N'、'S'、'E' 或者 'W'，分别表示向北、向南、向东、向西移动一个单位。

你从二维平面上的原点 (0, 0) 处开始出发，按 path 所指示的路径行走。

如果路径在任何位置上与自身相交，也就是走到之前已经走过的位置，请返回 true ；否则，返回 false 。

示例 1：

输入：path = "NES"
输出：false 
解释：该路径没有在任何位置相交。

示例 2：

输入：path = "NESWW"
输出：true
解释：该路径经过原点两次。

提示：

1 <= path.length <= 10⁴
path[i] 为 'N'、'S'、'E' 或 'W'

lightbulb

解题思路

方法一：哈希表

我们可以用一个哈希表 $vis$ 记录路径上的点。初始时 $vis$ 中只有原点 $(0, 0)$ 。

遍历字符串 $path$ ，对于每个字符 $c$ ，根据 $c$ 的值更新当前位置 $(i, j)$ ，然后判断 $(i, j)$ 是否在 $vis$ 中，如果在，则返回 true，否则将 $(i, j)$ 加入 $vis$ 中。

遍历结束后，返回 false。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为字符串 $path$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def isPathCrossing(self, path: str) -> bool:
        i = j = 0
        vis = {(0, 0)}
        for c in path:
            match c:
                case 'N':
                    i -= 1
                case 'S':
                    i += 1
                case 'E':
                    j += 1
                case 'W':
                    j -= 1
            if (i, j) in vis:
                return True
            vis.add((i, j))
        return False

speed

复杂度分析

指标	值
时间	O(n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Ability to recognize the importance of hashing for tracking visited points in path problems.
question_mark
Effective use of hash tables for fast lookups to detect repeated points.
question_mark
Clear understanding of the simulation pattern and its relation to path traversal problems.

warning

常见陷阱

外企场景

error
Failing to track the starting point (0, 0) as a visited location can lead to incorrect results.
error
Using inefficient data structures like arrays instead of hash tables, leading to slower performance for large inputs.
error
Not handling edge cases like very short paths (e.g., paths of length 1) or paths with only one direction.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the path involves diagonal moves, not just N, S, E, W?
arrow_right_alt
How would the solution change if the plane was 3D instead of 2D?
arrow_right_alt
What if the path has obstacles that block movement, and you need to account for those?

help

常见问题

外企场景

继续练习

#1487 保证文件名唯一 #1525 字符串的好分割数目 #1461 检查一个字符串是否包含所有长度为 K 的二进制子串