Given a string path, where path[i] = 'N', 'S', 'E' or 'W', each representing moving one unit north, south, east, or west, respectively. You start at the origin (0, 0) on a 2D plane and walk on the path specified by path.
Return true if the path crosses itself at any point, that is, if at any time you are on a location you have previously visited. Return false otherwise.
Example 1:
Input: path = "NES"
Output: false
Explanation: Notice that the path doesn't cross any point more than once.
Example 2:
Input: path = "NESWW"
Output: true
Explanation: Notice that the path visits the origin twice.
Constraints:
1 <= path.length <= 104
path[i] is either 'N', 'S', 'E', or 'W'.
判断路径是否相交。
给你一个字符串 path，其中 path[i] 的值可以是 'N'、'S'、'E' 或者 'W'，分别表示向北、向南、向东、向西移动一个单位。
你从二维平面上的原点 (0, 0) 处开始出发，按 path 所指示的路径行走。
如果路径在任何位置上与自身相交，也就是走到之前已经走过的位置，请返回 true ；否则，返回 false 。
思路
把坐标转换成一个字符串记录在 hashset，如果遇到重复的坐标则说明路径会相交，返回 true；否则返回 false。
复杂度
时间O(n)
空间O(n)
代码
Java实现
class Solution {
public boolean isPathCrossing(String path) {
Set<String> set = new HashSet<>();
int n = path.length();
int x = 0;
int y = 0;
set.add(x + "," + y);
for (int i = 0; i < n; i++) {
char cur = path.charAt(i);
if (cur == 'N') {
y++;
} else if (cur == 'S') {
y--;
} else if (cur == 'E') {
x++;
} else if (cur == 'W') {
x--;
}
if (!set.add(x + "," + y)) {
return true;
}
}
return false;
}
}