Untitled
unknown
c_cpp
5 months ago
10 kB
4
Indexable
//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; } };
Editor is loading...
Leave a Comment