Word Break - Part 2 | Practice | GeeksforGeeks

    void print(vector<int>& v){
        for(auto ele : v)
            cout << ele << " ";
        cout<< endl;
    }
    void backtrack(int index, vector<int> ans){
        if(index == (ans.size() - 1)){
            print(ans);
            return;
        }
        for(int i = index; i < ans.size(); i++){
            swap(ans[index], ans[i]);
            backtrack(index+1, ans);
            swap(ans[index], ans[i]);
        }
    }

class Solution{
    public:
    void findPaths(int i, int j, vector<string>& paths ,string path, vector<vector<int>>& mat){
        if(i == mat.size()-1 && j == mat.size()-1)
        {
            paths.push_back(path);
            return;
        }
        int dx[4] = {0,1,0,-1};
        int dy[4] = {1,0,-1,0};
        char move[4] = {'R','D','L','U'};
        mat[i][j] = 0;
        for(int k = 0; k < 4; k++){
            int x = i + dx[k], y = j+ dy[k];
            if((x>=0 && x < mat.size() && y >= 0 && y < mat.size()) && mat[x][y] != 0){
                
                path.push_back(move[k]);
                findPaths(x, y, paths, path, mat);
                path.pop_back();
            }
        }
        mat[i][j] = 1;
    }
    vector<string> findPath(vector<vector<int>> &mat, int n) {
        // Your code goes here
        vector<string> paths;
        string path;
        if(mat[0][0] == 0)
            return paths;
        findPaths(0, 0, paths, path, mat);
        // sort(paths.begin(), paths.end());
        return paths;
        
    }
};

class Solution{
public:
    using vs = vector<string>; using um = unordered_map<string,bool>;
    void fun(int idx,um& dict, string& s, vs& ans,vs sentence, const int& n){
        if(idx == s.length()){
            string main;
            for(auto word : sentence)
                main += word + ' ';
            main.pop_back();
            ans.push_back(main);
            return;
        }
        string temp = "";
        for(int i = idx; i < s.length(); i++){
            temp.push_back(s[i]);
            if(dict[temp]){
                sentence.push_back(temp);
                fun(i+1, dict, s, ans, sentence, n);
                sentence.pop_back();
            }
        }
    }
    vector<string> wordBreak(int n, vector<string>& d, string s)
    {
        // code here
        um dict;
        for(auto word : d)
            dict[word] = true;
        vs ans;
        vs sentence;
        fun(0, dict, s, ans, sentence, n);
        return ans;
    }
};

class Solution{
  public:
    int solve(int price[], int n , vector<int>& dp, int idx){
        if( idx >= n)   return 0;
        if(dp[idx] != -1) return dp[idx];
        int ans = 0;
        for(int i = 1; i <= n - idx; i++){
            ans = max(ans, price[i - 1] + solve(price, n , dp, idx + i));
        }
        return dp[idx] = ans;
    }
    int cutRod(int price[], int n) {
        //code here
        vector<int> dp;
        dp.resize(n, -1);
        return solve( price,n, dp, 0);
    }
};

class Solution {
  public:
    string longestPalin (string S) {
        // code here
        if(S.length() == 0)
            return "";
        string ans;
        pair<int,int> r{0,0};
        int len = 1, n = S.length();
        for(int i = 0 ; i < n; i++){
            int j = i, k =i;
            while(j-1 >= 0 && k+1 < n){
                if(!(S[j-1] == S[k+1]))
                    break;
                j--,k++;
            }
            int l1 = k - j + 1;
            pair<int,int> p1{j,k},p2{i,i};
            int l2 = 1;
            if( i +1 < n){
                bool f = (S[i] == S[i+1]);
                if(f){
                    j = i, k = i+1;
                    while( j-1 >=0 && k+1 < n){
                        if(!(S[j-1] == S[k+1]))
                            break;
                        j--,k++;
                    }
                    l2 = k - j + 1;
                    p2 = {j,k};
                }
            }
            if(len < max(l1,l2)){
                len = max(l1,l2);
                r = (l1 > l2)?p1:p2;
            }
        }
        for(int i = r.first; i<=r.second;i++)
            ans += S[i];
        return ans;
    }
};

class Solution {
public:
    int numOfWays(vector<int>& nums) {
        int m = nums.size();
        
        table.resize( m + 1);
        for(int i = 0; i < m + 1; ++i){
            table[i] = vector<long long> (i+1, 1);
            for(int j = 1; j < i ; ++j)
                table[i][j] = (table[i-1][j-1] + table[i-1][j])%mod;
        }
        return (dfs(nums) - 1) % mod;
    }
private:
    vector<vector<long long>> table;
    long long mod = 1e9+7;
    
    long long dfs(vector<int>& nums){
        int m = nums.size();
        if( m  < 3)
            return 1;
        vector<int> leftNodes, rightNodes;
        for(int i = 1; i < m ; i++){
            if( nums[i] < nums[0])
                leftNodes.push_back(nums[i]);
            else
                rightNodes.push_back(nums[i]);
        }
        long long leftWays = dfs(leftNodes) % mod;
        long long rightWays = dfs(rightNodes) % mod;
        return (((leftWays * rightWays) % mod) * table[m-1][leftNodes.size()])%mod;
    }
};

class Solution {
public:
    const int mod = 1e9 + 7;
    int m, n;
    vector<int> dx{1,0,0,-1},dy{0,1,-1,0};
    bool isValid(int x, int y){
        return x >= 0 and x < m and y >= 0 and y < n;
    }
    int dfs(int x, int y, vector<vector<int>>& grid, vector<vector<int>>& dp){
        if(dp[x][y] != -1)
            return dp[x][y];
        int ans = 1;
        for(int i = 0; i < 4; i++){
            int x_ = x + dx[i], y_ = y + dy[i];
            if(isValid(x_, y_) and grid[x_][y_] >grid[x][y])
                ans = (ans%mod + dfs(x_,y_,grid, dp)%mod)%mod;
        }
        return dp[x][y] = ans;
    }
    int countPaths(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m + 1, vector<int> ( n + 1, -1));
        int ans = 0;
        for(int i = 0; i < m; i++)
            for(int j = 0;j <n ;j++)
                ans = (ans%mod + dfs(i, j,grid, dp));
        return ans;
    }
};

git reset 89f6c3d --hard

class Solution {
public:
    const int m = 1e9+7;
    using vvi = vector<vector<int>>;
    int countWays(int idx, int steps, int arrLen,vvi& dp){
        if(idx < 0 || idx >= arrLen)    return 0;
        if(steps == 0)
            if(idx != 0)  return 0;
            else return 1;
        if(dp[idx][steps] != -1)
            return dp[idx][steps];
        return dp[idx][steps] = ((countWays(idx,steps-1,arrLen,dp)%m + countWays(idx+1,steps-1,arrLen,dp)%m )%m+ countWays(idx-1,steps-1,arrLen,dp)%m)%m;
    }
    int numWays(int steps, int arrLen) {
        vvi dp;
        arrLen = min(steps/2+1,arrLen);
        dp.resize(arrLen + 1,vector<int>(steps+1, -1));
        return countWays(0, steps, arrLen,dp);
    }
};