Untitled

//Important Questions 

//Regex Matching
// in recursive dp when you know what to store but at same time you want empty also take map 
//calculate the answer and return in any cases also

class Solution {
public:
    bool dfs(int i, int j, map<pair<int, int>, bool>& cache, string& s, string& p) {
        // Check if the result for the current state is already cached
        if (cache.find({i, j}) != cache.end()) {
            return cache[{i, j}];
        }

        // If both strings are fully matched
        if (i >= s.size() && j >= p.size()) {
            return true;
        }

        // If the pattern is exhausted but the string is not
        if (j >= p.size()) {
            return false;
        }

        // Check if the current characters match or if the pattern has '.'
        bool match = (i < s.size() && (s[i] == p[j] || p[j] == '.'));

        // Handle the '*' in the pattern
        if ((j + 1) < p.size() && p[j + 1] == '*') {
            // Two cases:
            // 1. Ignore the '*' (move j by 2)
            // 2. Use the '*' (move i by 1 if there is a match)
            cache[{i, j}] = dfs(i, j + 2, cache, s, p) || (match && dfs(i + 1, j, cache, s, p));
            return cache[{i, j}];
        }

        // Handle a standard character match
        if (match) {
            cache[{i, j}] = dfs(i + 1, j + 1, cache, s, p);
            return cache[{i, j}];
        }

        // If no match is found, store and return false
        cache[{i, j}] = false;
        return false;
    }

    bool isMatch(string s, string p) {
        map<pair<int, int>, bool> cache;
        return dfs(0, 0, cache, s, p);
    }
};


///Guess the word --> we have all the pool , take the random word out and getMatches for this , 
//from the pool --> take the word --> getMatches --> find all possible secrets again having same match and do this again 
class Solution {
public:
    int getMatchCount(string s, string p){
        int count =0;
        for(int i=0;i<6;i++) if(s[i]==p[i]) count++;
        return count;
    }
    void findSecretWord(vector<string>& words, Master& master) {
        while(!words.empty()){
            string word = words[rand()%words.size()];
            int match = master.guess(word);
            if(match == 6) return;
            vector<string> temp;
            for(auto &i: words){
                if(getMatchCount(i,word) == match) temp.push_back(i);
            }
            words = temp;
        }
    }
};


//cross word puzzle,
//form all combination from left -> right and top to bottom and put it the set and and then compare it with string and rev string both if any matches then voila
//game over it is 

class Solution {
public:
    bool checkRegexMatch(string s , string p){
        if(s.length()!=p.length()) return false;
        for(int i=0;i<s.length();i++){
            if(s[i]!='.' && s[i]!=p[i]) return false;
        }
        return true;
    }
    bool placeWordInCrossword(vector<vector<char>>& board, string word) {
        int n = board.size();
        int m = board[0].size();
        set<string> collections;
        for(int i=0;i<n;i++){
            string temp = "";
            for(int j=0;j<m;j++){
               if(board[i][j]!='#'){
                 if(board[i][j] == ' ') temp+='.';
                 else temp+=board[i][j];
               }
               else{
                 if(temp.length()>0) collections.insert(temp);
                 temp = "";
               }
            }
            if(temp.length()>0) collections.insert(temp);
        }
        for(int j=0;j<m;j++){
            string temp = "";
            for(int i=0;i<n;i++){
               if(board[i][j]!='#'){
                 if(board[i][j] == ' ') temp+='.';
                 else temp+=board[i][j];
               }
               else{
                 if(temp.length()>0) collections.insert(temp);
                 temp = "";
               }
            }
            if(temp.length()>0) collections.insert(temp);
        }
        string oriWord = word;
        reverse(word.begin(),word.end());
        string revWord = word;
        for(auto &ite : collections){
            if(checkRegexMatch(ite,oriWord) || checkRegexMatch(ite,revWord)) return true;
        }
        return false;
    }
};


///Trie class with good understanding
class Node{
public:
    Node* links[26];
    bool flag = false;
};

class Trie{
private:
    Node* root;

public:

    Trie(){
        root = new Node();
    }

    void insert(string word){
        Node* temp = root;
        for(auto &i: word){
            if(temp->links[i-'a'] == NULL) {
                temp->links[i-'a'] = new Node();
            }
            temp = temp->links[i-'a'];
        }
        temp->flag = true;
    }

    bool search(string word){
        Node* temp = root;
        for(auto &i: word){
            if(temp->links[i-'a'] == NULL) return false;
            temp = temp->links[i-'a'];
        }
        return temp->flag;
    }

    bool startsWith(string prefix){
        Node* temp = root;
        for(auto &i: prefix){
            if(temp->links[i-'a'] == NULL) return false;
            temp = temp->links[i-'a'];
        }
        return true;
    }
}

//// Obstacle questions

// with obstacles had to check -> go from bottom to top 

// with obstacles but you can remove at most k obstacles::

// where you can visit nodes once only or where you can visit multiple times 

// obstacles ( remove k at max ) and no obstacles || visit only once || visit multiple times || can reach or not || minimum moves to reach || 
// minimum ways to reach also 

// ------------------------------------------------------------------------------------------------
//

///Grid questions
// - move from a to b --> no of steps ( bfs/dfs/graphs algos ) + no of ways (dp ki algo)
// - move from a to b --> visit one cell multiple times or single time --> no fo steps ( bfs/dfs) + no of ways (dp)

//Grid with obstacles 
// - move from a to b --> no. of steps (bfs/dfs) and no. of ways (dp ki algo)
// - move from a to b --> 

// obstacle and no obstacle
// visit once or visit multiple times
// remove k obstacles or none
// no of steps to reach ( bfs ) and no of ways[min/max] to reach (dp)




// You can remove max k obstacles, count the number of steps in this cases 
// do the bfs explore all ways, m[i,j,k] is needed why beacuse you can reach a cell with various k's and depending on which you can go further
// check had you already arrived this cell with (i,j,k-1) then don't visit else visit
// bfs.push // jab tak size>0 // front and pop // explore childrens // and push accordingly // decresing the count in same level // increase steps.

class Solution {
public:
    int shortestPath(vector<vector<int>>& grid, int k) {
        int n=grid.size();
        int m=grid[0].size();
        queue<pair<pair<int,int>,int>> bfsQ;
        map<tuple<int, int, int>, bool> vis;
        bfsQ.push({{0,0},k});
        vector<int> dx={-1,0,1,0};
        vector<int> dy={0,1,0,-1};
        int steps=0;
        while(!bfsQ.empty()){
            int levelSz=bfsQ.size();
            while(levelSz>0){
                pair<pair<int,int>,int> node=bfsQ.front();
                bfsQ.pop();
                int curR=node.first.first;
                int curC=node.first.second;
                int curK=node.second;
                if(curR==n-1 && curC==m-1) return steps;
                for(int i=0;i<4;i++){
                    int desR=curR+dx[i];
                    int desC=curC+dy[i];
                    if(desR<n && desR>=0 && desC>=0 && desC<m){
                        if(grid[desR][desC]==0 && vis.find({desR,desC,curK})==vis.end()){
                            bfsQ.push({{desR,desC},curK});
                            vis[{desR,desC,curK}]=true;
                        }
                        else if(grid[desR][desC]==1 && curK>0 && vis.find({desR,desC,curK-1})==vis.end()){
                            bfsQ.push({{desR,desC},curK-1});
                            vis[{desR,desC,curK-1}]=true;
                        }
                    }
                }
                levelSz--;
            }
            steps++;
        }
        return -1;
    }
};

//Backtracking questions 
//Point diye hue the rectangle ka area nikalna hai perpendicular   

// N Queens problem 

class Solution 
{
public:
    bool issafe(int row,int col,int n,vector<int>& rowhash,vector<int>& upperhash,vector<int>& lowerhash)
    {
        if(rowhash[row]==1||upperhash[row+col]==1||lowerhash[n-1+(col-row)]==1) return false;
        return true;
    }
    void nqueen(int col,int n,vector<vector<char>>& v,vector<vector<string>>& ans, vector<int>& rowhash,vector<int>& upperhash,vector<int>& lowerhash)
    {
        if(col==n)
        {
            vector<string> temp;
            for(int i=0;i<v.size();i++)
            {
                string ttemp;
                for(int j=0;j<v[i].size();j++)
                {
                    ttemp.push_back(v[i][j]);
                }
                temp.push_back(ttemp);
            }
            ans.push_back(temp);
            return;
        }
        for(int row=0;row<n;row++)
        {
            if(issafe(row,col,n,rowhash,upperhash,lowerhash))
            {
                v[row][col]='Q';
                rowhash[row]=1;
                upperhash[row+col]=1;
                lowerhash[n-1+(col-row)]=1;
                nqueen(col+1,n,v,ans,rowhash,upperhash,lowerhash);
                v[row][col]='.';
                rowhash[row]=0;
                upperhash[row+col]=0;
                lowerhash[n-1+(col-row)]=0;
            }
        }
        return;
    }
    vector<vector<string>> solveNQueens(int n) 
    {
        vector<vector<string>> ans;
        vector<vector<char>> v(n,vector<char>(n,'.'));//n*n matrix
        vector<int> rowhash(n,0),upperhash((2*n)-1,0),lowerhash((2*n)-1,0);
        nqueen(0,n,v,ans,rowhash,upperhash,lowerhash);
        return ans;
    }
};