Judging whether paths intersect or not by leetcode

Want to make APP Same thing as WeChat , Can run small programs smoothly ？ | Experience will send you to Xinjiang 、 Huawei 、 Cherry keyboard ！>>>

order

This article mainly records leetcode Whether the paths intersect

subject

 Give you a string  path, among  path[i]  The value of can be  'N'、'S'、'E'  perhaps  'W', To the north 、 Southward 、 To the east 、 Move one unit West .

 The robot starts from the origin on the two-dimensional plane  (0, 0)  Starting from , Press  path  The path indicated to walk .

 If paths intersect at any point , That is to go to the position that has been passed before , Please return  True ; otherwise , return  False .

 source ： Power button （LeetCode）
 link ：https://leetcode-cn.com/problems/path-crossing
 Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Answer key

class Solution {
    public boolean isPathCrossing(String path) {
        int x = 0;
        int y = 0;
        Set<String> pathSet = new HashSet<String>();
        pathSet.add("00");
        for (char c : path.toCharArray()) {
            if (c == 'N') {
                y++;
            } else if (c == 'S') {
                y--;
            } else if (c == 'W') {
                x--;
            } else if (c == 'E') {
                x++;
            }
            String p = String.valueOf(x) + String.valueOf(y);
            if (pathSet.contains(p)) {
                return true;
            }
            pathSet.add(p);
        }
        return false;
    }
}

Summary

Here to maintain the past point , Then traverse path The characters of , Yes x,y The coordinates move accordingly , After each move, judge whether the point has passed , Walk past and return true, If not, record the change points in the past points , After traversing, it will return if it does not meet the conditions false.

doc

• Determine whether the paths intersect