loading...

Daily Coding Challenge #47

wingkwong profile image Wing-Kam ・3 min read

About

This is a series of Daily Coding Challenge. Each day I show a few solutions written in C++. The questions are from coding practice/contest sites such as HackerRank, LeetCode, Codeforces, Atcoder and etc.


/*
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'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}
*/

class Solution {
public:
    bool isPathCrossing(string path) {
        unordered_map<int,unordered_map<int, int>> m;
        int x=0,y=0;
        // origin point
        m[x][y]=1;
        for(char c:path){
            if(c=='N') y+=1;
            else if(c=='E') x+=1;
            else if(c=='S') y-=1;
            else if(c=='W') x-=1;
            // check if it s visited
            if(m[x][y]) return true;
            // if not, set it visited
            m[x][y]=1;
        }
        return false;
    }
};

/*
LeetCode - Unique Paths
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?


Above is a 7 x 3 grid. How many possible unique paths are there?

Example 1:

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right
Example 2:

Input: m = 7, n = 3
Output: 28


Constraints:

1 <= m, n <= 100
It's guaranteed that the answer will be less than or equal to 2 * 10 ^ 9.
*/


class Solution {
public:
    int uniquePaths(int m, int n) {
        // store how many ways to reach arr[m][n]
        int dp[m][n];
        // for col=0, there is only one way to reach 
        for(int i=0;i<m;i++) dp[i][0]=1;
        // for row=0, there is only one way to reach
        for(int j=0;j<n;j++) dp[0][j]=1;
        // traverse the rest of the cells
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                // since the possible move is either from the top and from the left 
                // so combine them together : dp[i-1][j] (from the top) +  dp[i][j-1] (from the left)
                dp[i][j]= dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
};

The source code is available in corresponding repo below. Star and watch for timely updates!

GitHub logo wingkwong / leetcode

🏆 A Collection of my LeetCode Solutions with Explanations 🏆

GitHub logo wingkwong / hackerrank

🏆 A Collection of my HackerRank Solutions with Explanations 🏆

GitHub logo wingkwong / codeforces

🏆 A Collection of my Codeforces Solutions with Explanations 🏆

GitHub logo wingkwong / atcoder

🏆 A Collection of my AtCoder Solutions with Explanations 🏆

Posted on by:

wingkwong profile

Wing-Kam

@wingkwong

Consultant by day. Developer by night. AWS certified. Exploring #CloudNative currently.

Discussion

pic
Editor guide