判断路径是否相交
难度:
标签:
题目描述
给你一个字符串 path，其中 path[i] 的值可以是 'N'、'S'、'E' 或者 'W'，分别表示向北、向南、向东、向西移动一个单位。
你从二维平面上的原点 (0, 0) 处开始出发，按 path 所指示的路径行走。
如果路径在任何位置上与自身相交，也就是走到之前已经走过的位置，请返回 true ；否则，返回 false 。
示例 1：
输入：path = "NES" 输出：false 解释：该路径没有在任何位置相交。
示例 2：
输入：path = "NESWW" 输出：true 解释：该路径经过原点两次。
提示：
1 <= path.length <= 104path[i]为'N'、'S'、'E'或'W'
代码结果
运行时间: 23 ms, 内存: 0.0 MB
// 思路：使用Java Stream的方式进行集合操作。在每一步移动后检查位置是否已存在于集合中。
import java.util.*;
import java.util.stream.*;
public class Solution {
public boolean isPathCrossing(String path) {
Set<String> visited = new HashSet<>();
int[] position = {0, 0};
visited.add(position[0] + "," + position[1]);
return path.chars().mapToObj(c -> {
switch (c) {
case 'N': position[1]++; break;
case 'S': position[1]--; break;
case 'E': position[0]++; break;
case 'W': position[0]--; break;
}
return position[0] + "," + position[1];
}).anyMatch(pos -> !visited.add(pos));
}
}解释
方法:
这个题解利用了哈希集合来记录所有已经访问过的坐标位置。首先，定义一个字典 d 来将方向 ('N', 'E', 'S', 'W') 映射到相应在平面上的坐标变化。接着，使用一个集合 seen 来存储所有已经经过的坐标点，默认先将原点 (0, 0) 加入集合。对于路径 path 中的每一个方向，根据字典 d 获取相应的坐标偏移，更新当前坐标 (x, y)。如果更新后的坐标已经存在于 seen 集合中，说明路径相交，函数返回 true。如果循环结束后没有发现相交，返回 false。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在题解中，为什么选择使用集合（set）来存储已访问的坐标，而不是使用列表（list）或字典（dictionary）？
▷🦆
题解中提到的字典`d`映射方向到坐标变化，能否具体解释这种映射是如何工作的，以及它如何与路径字符串中的字符交互？
▷🦆
题解中提到，如果更新后的坐标已经存在于`seen`集合中，则返回`true`。这种方法是否能够立即检测到所有类型的路径交叉，还是只适用于某些特定情况？
▷🦆
在题解中，是如何处理路径中可能存在的无效字符或错误方向的？例如，如果路径字符串包含除`'N', 'E', 'S', 'W'`之外的其他字符。
▷