LeetCode 1496: Path Crossing (Hash Set Path Replay)
LeetCode 1496Hash SetSimulationToday we solve LeetCode 1496 - Path Crossing.
Source: https://leetcode.com/problems/path-crossing/
English
Problem Summary
Given a path made of N, S, E, and W steps from origin (0,0), return true if any position is visited more than once; otherwise return false.
Key Insight
Only visited coordinates matter. If we replay each move and a coordinate appears again, the path crosses itself immediately.
Brute Force and Limitations
A naive way compares each new position against all previous positions, which costs O(n²). We can do better with hashing.
Optimal Algorithm Steps
1) Start at (0,0) and put it into a visited set.
2) Replay each character and update (x,y).
3) If new (x,y) is already in set, return true.
4) Otherwise insert it and continue; if finished, return false.
Complexity Analysis
Time: O(n) because each step does O(1) expected hash work.
Space: O(n) for visited coordinates.
Common Pitfalls
- Forgetting to insert the origin before traversal.
- Updating coordinates with wrong direction signs.
- Encoding coordinates ambiguously (use a delimiter or tuple).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public boolean isPathCrossing(String path) {
Set<String> seen = new HashSet<>();
int x = 0, y = 0;
seen.add("0,0");
for (char c : path.toCharArray()) {
if (c == 'N') y++;
else if (c == 'S') y--;
else if (c == 'E') x++;
else x--; // 'W'
String key = x + "," + y;
if (!seen.add(key)) {
return true;
}
}
return false;
}
}func isPathCrossing(path string) bool {
x, y := 0, 0
seen := map[string]bool{"0,0": true}
for _, c := range path {
switch c {
case 'N':
y++
case 'S':
y--
case 'E':
x++
case 'W':
x--
}
key := fmt.Sprintf("%d,%d", x, y)
if seen[key] {
return true
}
seen[key] = true
}
return false
}class Solution {
public:
bool isPathCrossing(string path) {
int x = 0, y = 0;
unordered_set<string> seen;
seen.insert("0,0");
for (char c : path) {
if (c == 'N') ++y;
else if (c == 'S') --y;
else if (c == 'E') ++x;
else --x; // 'W'
string key = to_string(x) + "," + to_string(y);
if (seen.count(key)) return true;
seen.insert(key);
}
return false;
}
};class Solution:
def isPathCrossing(self, path: str) -> bool:
x = y = 0
seen = {(0, 0)}
for c in path:
if c == 'N':
y += 1
elif c == 'S':
y -= 1
elif c == 'E':
x += 1
else: # 'W'
x -= 1
point = (x, y)
if point in seen:
return True
seen.add(point)
return Falsevar isPathCrossing = function(path) {
let x = 0, y = 0;
const seen = new Set(["0,0"]);
for (const c of path) {
if (c === 'N') y++;
else if (c === 'S') y--;
else if (c === 'E') x++;
else x--; // 'W'
const key = `${x},${y}`;
if (seen.has(key)) {
return true;
}
seen.add(key);
}
return false;
};中文
题目概述
给定只包含 N、S、E、W 的路径字符串，从原点 (0,0) 出发。若某个坐标被访问超过一次，返回 true；否则返回 false。
核心思路
核心只看“坐标是否重复出现”。按顺序重放路径，一旦到达已访问坐标，就说明路径发生交叉。
暴力解法与不足
朴素做法是每走一步都和历史所有坐标比较，时间复杂度 O(n²)。使用哈希集合可降到线性。
最优算法步骤
1）初始化坐标为 (0,0)，并先加入 visited。
2）逐字符移动并更新 (x,y)。
3）若新坐标已在 visited 中，立即返回 true。
4）否则加入集合继续遍历，结束后返回 false。
复杂度分析
时间复杂度：O(n)（哈希操作期望 O(1)）。
空间复杂度：O(n)。
常见陷阱
- 忘记先记录起点 (0,0)。
- 方向与坐标增减写反。
- 坐标序列化不规范导致冲突。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public boolean isPathCrossing(String path) {
Set<String> seen = new HashSet<>();
int x = 0, y = 0;
seen.add("0,0");
for (char c : path.toCharArray()) {
if (c == 'N') y++;
else if (c == 'S') y--;
else if (c == 'E') x++;
else x--; // 'W'
String key = x + "," + y;
if (!seen.add(key)) {
return true;
}
}
return false;
}
}func isPathCrossing(path string) bool {
x, y := 0, 0
seen := map[string]bool{"0,0": true}
for _, c := range path {
switch c {
case 'N':
y++
case 'S':
y--
case 'E':
x++
case 'W':
x--
}
key := fmt.Sprintf("%d,%d", x, y)
if seen[key] {
return true
}
seen[key] = true
}
return false
}class Solution {
public:
bool isPathCrossing(string path) {
int x = 0, y = 0;
unordered_set<string> seen;
seen.insert("0,0");
for (char c : path) {
if (c == 'N') ++y;
else if (c == 'S') --y;
else if (c == 'E') ++x;
else --x; // 'W'
string key = to_string(x) + "," + to_string(y);
if (seen.count(key)) return true;
seen.insert(key);
}
return false;
}
};class Solution:
def isPathCrossing(self, path: str) -> bool:
x = y = 0
seen = {(0, 0)}
for c in path:
if c == 'N':
y += 1
elif c == 'S':
y -= 1
elif c == 'E':
x += 1
else: # 'W'
x -= 1
point = (x, y)
if point in seen:
return True
seen.add(point)
return Falsevar isPathCrossing = function(path) {
let x = 0, y = 0;
const seen = new Set(["0,0"]);
for (const c of path) {
if (c === 'N') y++;
else if (c === 'S') y--;
else if (c === 'E') x++;
else x--; // 'W'
const key = `${x},${y}`;
if (seen.has(key)) {
return true;
}
seen.add(key);
}
return false;
};
Comments