1496. Path Crossing.md

1496. Path Crossing

---

the first one in Weekly Contest 195

---

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've 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 <= 10^4
• path will only consist of characters in {'N', 'S', 'E', 'W}

---

Solution

• mine
  • Java
    • Runtime: 4 ms, faster than 50.00%, Memory Usage: 40.2 MB, less than 100.00% of Java online submissions

      // O(N)time O(N)space
      // N = path.length()
      public boolean isPathCrossing(String path) {
          HashSet<String> set = new HashSet<>();
          set.add("0,0");
          int x = 0, y = 0;
          char[] arr = path.toCharArray();
          for(char c : arr){
              if(c == 'N' || c == 'S'){
                  y += c == 'N' ? 1 : -1;
              }else{
                  x += c == 'E' ? 1 : -1;
              }
              String t = x + "," + y;
              if(set.contains(t)){
                  return true;
              }else{
                  set.add(t);
              }
          }
          return false;
      }
      

---