2023-12-23 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's December LeetCoding Challenge with cpp.

December LeetCoding Challenge 23

Description

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'.

Solution

auto speedup = [](){
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();
class Solution {
  map<char, int> mp= {
    { 'N', 10000 },
    { 'S', -10000 },
    { 'W', 1 },
    { 'E', -1 }
  };
public:
  bool isPathCrossing(string path) {
    set<int> position{ 0 };
    int current = 0;
    for(auto d : path) {
      current += mp[d];
      if(position.count(current)) {
        return true;
      }
      position.insert(current);
    }
    return false;
  }
};

// Accepted
// 81/81 cases passed (0 ms)
// Your runtime beats 100 % of cpp submissions
// Your memory usage beats 64.64 % of cpp submissions (7.2 MB)
Algorithm