[LeetCode] 1496. Path Crossing

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;
    }
}