Easy

题目描述

给你一个字符串 path，其中 path[i] = 'N'、'S'、'E' 或者 'W'，分别表示向北、向南、向东、向西移动一个单位。你从二维平面上的原点 (0, 0) 开始出发，按 path 所指示的路径行走。

如果路径在任何位置上与自身交叉，也就是说，如果你曾经走到过同一个位置，请返回 true；否则，返回 false。

示例 1：

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

示例 2：

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

约束条件：

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

提示：

  • 模拟移动过程，同时跟踪访问过的点。
  • 使用集合来存储之前访问过的点。

解题思路

这道题考查的是模拟行走过程并检测路径是否重复经过同一点的问题。

解题思路

核心思想：在模拟行走过程中，记录每个访问过的坐标点，如果发现当前位置之前已经访问过，则说明路径发生了交叉。

算法步骤：

  1. 从原点 (0, 0) 开始，将起始位置加入已访问集合
  2. 根据路径字符串中的每个字符，更新当前坐标：
    • ‘N’：y 坐标 +1（向北）
    • ‘S’：y 坐标 -1（向南）
    • ‘E’：x 坐标 +1（向东）
    • ‘W’：x 坐标 -1（向西）
  3. 每次移动后，检查新位置是否在已访问集合中
  4. 如果已存在，返回 true；否则将新位置加入集合
  5. 遍历完成后返回 false

时间复杂度：O(n)，其中 n 是路径长度，需要遍历每个字符 空间复杂度：O(n)，最坏情况下需要存储所有访问过的位置

这是一个典型的哈希表应用题，通过集合来高效判断坐标是否重复访问。

代码实现

class Solution {
public:
    bool isPathCrossing(string path) {
        set<pair<int, int>> visited;
        int x = 0, y = 0;
        visited.insert({x, y});
        
        for (char c : path) {
            if (c == 'N') y++;
            else if (c == 'S') y--;
            else if (c == 'E') x++;
            else if (c == 'W') x--;
            
            if (visited.count({x, y})) {
                return true;
            }
            visited.insert({x, y});
        }
        
        return false;
    }
};

class Solution:
    def isPathCrossing(self, path: str) -> bool:
        visited = set()
        x, y = 0, 0
        visited.add((x, y))
        
        for direction in path:
            if direction == 'N':
                y += 1
            elif direction == 'S':
                y -= 1
            elif direction == 'E':
                x += 1
            elif direction == 'W':
                x -= 1
            
            if (x, y) in visited:
                return True
            visited.add((x, y))
        
        return False

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

var isPathCrossing = function(path) {
    let visited = new Set();
    let x = 0, y = 0;
    visited.add("0,0");
    
    for (let i = 0; i < path.length; i++) {
        if (path[i] === 'N') y++;
        else if (path[i] === 'S') y--;
        else if (path[i] === 'E') x++;
        else if (path[i] === 'W') x--;
        
        let pos = x + "," + y;
        if (visited.has(pos)) return true;
        visited.add(pos);
    }
    
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历路径字符串的每个字符，哈希表的查找和插入操作均为 O(1)
空间复杂度O(n)最坏情况下需要存储所有 n 个不同的访问位置