难度: Easy
给你一个字符串 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
class Solution:
def isPathCrossing(self, path: str) -> bool:
d = dict(zip('NESW', [(0, 1), (1, 0), (0, -1), (-1, 0)]))
x, y, seen = 0, 0, {(0, 0)}
for i, j in map(d.get, path):
x, y = x + i, y + j
if (x, y) in seen:
return True
seen.add((x, y))
return False
这个题解利用了哈希集合来记录所有已经访问过的坐标位置。首先，定义一个字典 d 来将方向 ('N', 'E', 'S', 'W') 映射到相应在平面上的坐标变化。接着，使用一个集合 seen 来存储所有已经经过的坐标点，默认先将原点 (0, 0) 加入集合。对于路径 path 中的每一个方向，根据字典 d 获取相应的坐标偏移，更新当前坐标 (x, y)。如果更新后的坐标已经存在于 seen 集合中，说明路径相交，函数返回 true。如果循环结束后没有发现相交，返回 false。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def isPathCrossing(self, path: str) -> bool:
# 映射方向到坐标变化的字典
d = dict(zip('NESW', [(0, 1), (1, 0), (0, -1), (-1, 0)]))
# 初始化坐标和已见坐标集合
x, y, seen = 0, 0, {(0, 0)}
# 遍历路径字符
for i, j in map(d.get, path):
# 更新坐标
x, y = x + i, y + j
# 检查新坐标是否已见
if (x, y) in seen:
return True
# 添加新坐标到集合
seen.add((x, y))
return False
使用集合（set）来存储已访问的坐标主要是因为集合在查找和插入操作中提供了更高的效率。集合的底层实现通常是基于哈希表，这使得平均时间复杂度为O(1)。相比之下，使用列表存储坐标时，检查一个坐标是否已存在的操作需要O(n)时间复杂度，因为需要遍历整个列表。虽然字典（dictionary）也可以达到O(1)的查找和插入效率，但使用集合更为直接和简洁，因为它只需要关注坐标的存在性，而不需要存储额外的键值对数据。
在题解中，字典`d`被用来映射字符方向（'N', 'E', 'S', 'W'）到对应的平面坐标变化。具体来说，'N'对应于(0, 1)表示向北移动，增加y坐标；'E'对应于(1, 0)表示向东移动，增加x坐标；'S'对应于(0, -1)表示向南移动，减小y坐标；'W'对应于(-1, 0)表示向西移动，减小x坐标。在遍历路径字符串时，每个字符被用作键来从字典`d`中检索相应的坐标偏移。然后，这些坐标偏移被用来更新当前位置，从而实现路径的跟踪。
这种使用集合来检测路径交叉的方法可以立即检测到所有类型的路径交叉。一旦某个坐标在之前已经被添加到集合中，这表示路径曾经经过这个点。如果在任何时刻，新的坐标更新后发现已存在于集合中，这就意味着路径在此之前已经访问过这个坐标，即发生了路径交叉。此方法对所有情况都有效，无论路径如何移动。
题解中没有明确说明如何处理包含无效字符的情况。在实际应用中，如果路径字符串可能包含无效字符，应当在遍历路径前或在处理每个字符时进行验证。例如，可以在迭代每个方向字符之前检查其是否有效（即是否为'N', 'E', 'S', 'W'中的一个）。如果发现无效字符，可以抛出异常或返回错误信息。这需要在实现中额外添加错误处理机制来确保路径的有效性。