Find particular properties based on the abstracted decision tree or abstracted graph.
The input data is not the explicit tree with Tree node for questions listed in this blog. For the string structure, it may use some ideas like sliding window with loer bound and upper bound as the mechanism to search things, we do not list them here, we mainly list the question with the decision tree or graph in an logical way but the input is not the not the explicit tree structure.
Extracting decision tree from the actual problem. One difficulty with the search problem is that we need to extract the decision tree logically from different problem contexts. Typical scenarios are 1> the binary tree type, which decide add or not add current character. Each node represent choose or not choose here 2> Each node represents an actual character as the tree node, such as the permulation problems or combination of different cases. 4> Each intermediat node can represents the path, or part of the answer, such as 17, when moving to the leaf node, then inserting answer. 5> Each node represents the derived results about the given input, a little bit similar to the reduction opetaion, such as 241, the resutls can be a set contains all possible solutions.
Using DFS or BFS, we can decide to use BFS or DFS from several aspects:
For the tree node expression, the BFS case might need to use a customized tree node (which is rarely used in leetcode questions), usually use the pair or tuple if we need multiple variables in the tree node. For the DFS code, there are less restrictions since we basically hide the tree node inexplicitly in the function call. We can transfer the necessary variables used in each call by function parameters. We can also set some varaibles as the class variables to avoid transfering them by tree node and simplify the code a little bit.
Time complexity and if there is explicit layered structure. Although both the time compexity is O(V+E), the DFS is suitable for the narrow long tree, ans the BFS is suitable for the wide and short tree. In practical case, we may need to evaluate the data scale of the leetcode question, this may decide which algorithm is used for the giving data sets. This is tricky and is easy to be neglected when we start to code in in a rush without considering time compexity in advance carefully.
If the question shows an obvious layered structure, the BFS can be more approporiate. For example, we find the minimal path with the particular constrians, we use the BFS, once find the path, we return it direactly. These type of questions are typical BFS style, and the BFS can ususlly save more efficient for solving these type of questions.
BFS is more approporiate for the question with the abstraction of the distance or shortest path. We try to find a shortest path from the root. For the question there is a cycle, the BFS might be suitable. Since there is no unique layered structure in the case where there is cycle, and the level can be different if we go through along the different path (such as 79).
For the DFS solution, pay attention that if we need return sth from the child tree. Namely make sure which is more convenient, either top to bottom operation (the previous informaion in the path can be used to determin the subsequent nodes in the path) or bottom to up operation. The core idea is to make sure what are computation processed in each node (is it merging two results from subtree or divide the current results to two subtree). It is worth noting that, for the bottom to up case, we can only use the DFS since it keep the status of the current node, so we can update the status when getting back results from the subtree. For the BFS, it just pop the parent out during the traverse process and we can not further update the previous status of the nodes. For the DFS case, there are three typical design: (a) Check all solutions and return void, put the valid path into a separate ans (b) Return true or false, we only need to find one path in this case, if we find the valid path, just return true (such as 37) (c) Return a specific value for each dfs call, maybe a reduced integer or more complex results such as a set.
Set back the status. It is important to always check if we set the status back for the dfs operation. For example, a> when we find specific path, remember to pop the current node back from the ans if we insert it for the current layer (make sure the pop_back match with the insert, otherwise, there might be the memory issue). b> The status can also be the flag variable that label if a specific character is visited or not. c> In the for loop scenarios, we need to make sure the status if set back to the parent case before calling the dfs operations each time.
If there is no difference between the aspects discussed above, we can either use BFS or DFS. And using DFS might be more easier from coding’s perspective if we write it into a recursive way instead of using a stack.
One typical type of question based on dfs or backtracking, 77 and 282 are two typical one (how current solution can come from previous solutions in small scale). The general framework for decomposing is to use a for loop, and each time in the for loop for processing element, the principle is the start position or end position of the string. For 77, we compute all combination, the start position is the root node, the end position can be each element in the string. For 282, we extract all possible operand, the start position of operand can be current index and the end position can be 1 to the end of the whole string.
TODO, two basic use case for bfs, the shortest path, the visited flag(no flag, might be the infinity loop in matrix search) , the queue size is the number of element in current layer !! 675 is good one that includes all typical problems.
Commonly used debug strategy. This part of question is error prone and some small type of condition error can lead to totally different results. Start from the small scale case or print out the traverse path explicitly are commonly used strategies.
Commonly used optimization strategy or trimming strategy. Sort the input array. Using flag to label the status of associated elements. Using map to memorize existing path (if the key and values are clear). Avoid the unnecessary string copy.
Ensentially the bfs or dfs questions discussed this part can process the unweighted graph. For the question which can be abstracted as the weighted graph, we need to use more complex mechanism to do that such as the dp method to acclerate the searching process (such as dp approach of the 943), refer to this https://zxi.mytechroad.com/blog/searching/leetcode-675-cut-off-trees-for-golf-event/, when there is no new node, then layer ++, we can save one variable by this way, otherwise, we need to save it in the bfs node each time we traverse the tree. (this is really important), maybe using 1091 as a templaete question
Be careful about using the vector<bool> when you need to use a flag array. There are lots of discussion online, you may just use the vector<int> for simplicity or use the bit mask if the flag length is fixed. Using the vector<bool> can slow down the your code heavily (a least 10x times slower compared with usinig the vector<int>) 996 is a good example (three important conditions) to discuss about how to set the flag to make sure how the same node can be visited once in the same level.
A tip for checking the associated elements in 2d case. We might check the element at the different direaction such as up down left and right even for slash direaction sometimes, instead of go through each dimention separately, the good way is to initilize a 2d vector, such as (-1,1),(1,-1)... , in cpp it is vector<vector<int>> dir = {{-1,1},{1,1},{-1,-1},{1,-1}}; then we use one loop to range this vector and adjust the x and y coordinates accordingly. This method is more simple to check the different direction of the 2d grid (Related question: 51).
Naive DFS-UpToBottom-Combination
The nature of the combination is the cartision product, we may need to have an idea about the set. Then the results of the combination might be to do the cartision products between different sets. It is important to figure out what are avalible set for some questions with complex background.
39. Combination Sum
This is the recursion version, which is really fast. For this recursion version based on dfs, the pop out operation at the end of dfs call is really important. Sorting the input array is an important techniques, sometimes, it can trim the searching tree (when the target value is negative one we trim the tree). The key idea to make sure that the elements can be used multiple times is that for each step of creating the children node, we go through all possible options no matter it is visited or not.
Another key point is that, if we do not use the sort, we may have repeated resutls such as [2,3,3] and [3,2,3]. From the implementaion perspective, using the remain value, and we decrease it gradually (instead of sum value) can be more convenient. Otherwise, we need to check if the current path exists in the ans set (we need to sort the array and check back and forth, which is redundant)
voiddfs(vector<int>& candidates, int target, int s, vector<int>& cur, vector<vector<int>>& ans){ if(target==0){ ans.push_back(cur); return; } for(int i=s;i<candidates.size();i++){ if(candidates[i]>target){ //current path not valid continue; } cur.push_back(candidates[i]); dfs(candidates, target-candidates[i], i, cur, ans); //set back to original status cur.pop_back(); } return; } };
We can also use the BFS for this simple context, but for this question, there is no obvious benifits for using the BFS, since we need to search all possible solutions. However, it needs some difficuties to process the intermidiate node. Using the targetNew value as the distinction for different strategies is important. (how to define the control block is important)
classSolution { structNode { Node(vector<int> path, int target, int index) : m_path(path), m_target(target), m_index(index){} vector<int> m_path; int m_target; int m_index; }; public: vector<vector<int>> combinationSum(vector<int>& candidates, int target) { queue<Node> q; vector<vector<int>> ans; //avoid the repeated answer such as [2,3,3] and [3,2,3] sort(candidates.begin(), candidates.end()); int len = candidates.size(); // init the q for (int i = 0; i < len; i++) { int v = candidates[i]; int targetnew = target - v; Node d({v}, targetnew, i);
while (q.empty() == false) { int levelSize = q.size(); // go through the queue while (levelSize > 0) { Node node = q.front(); //there should not be the i //it should be the value of the parent for (int j = node.m_index; j < len; j++) { int vnew = candidates[j]; int targetNew = node.m_target - vnew; vector<int> pathNew = node.m_path; pathNew.push_back(vnew); // push the satiafied results into the ans // push the valid results into the next level if (targetNew > 0) { Node nodnew(pathNew, targetNew, j); q.push(nodnew); } elseif (targetNew == 0) { ans.push_back(pathNew); } // targetNew < 0 // do nothing for this case // do not push subsequent nodes } q.pop(); levelSize--; } } } return ans; } };
40. Combination Sum II
This one is similar with previous one, but the only difference is that the element is not unique in the input string, we add some constrains to avoid the repeated ans. The sorting operation is still necessary, we just skip the current element if it has been visited.
classSolution { public: vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { vector<vector<int>> ans; vector<int> curr; sort(candidates.begin(),candidates.end()); dfs(ans,candidates,0,target,curr, true); return ans; } voiddfs(vector<vector<int>>& ans, vector<int>& candidates, int start, int target, vector<int>& curr, bool firstlayer){ //dfs children for(int i=start;i<candidates.size();i++){ // if i is in visited, jump // attention, it is the i>start here if(i>start && candidates[i]==candidates[i-1]){ continue; } int targetNew = target-candidates[i]; if(targetNew<0){ continue; }elseif(targetNew==0){ curr.push_back(candidates[i]); ans.push_back(curr); curr.pop_back(); continue; }else{ //targetNew >0 //visit current node curr.push_back(candidates[i]); //dfs dfs(ans,candidates,i+1,targetNew, curr, false); curr.pop_back(); } } return; } };
77. Combinations
The idea is similar with previous one. Be careful the meaning of the n and k. This can be viewed as the basic one for this type of question. Using the dfs can make things much more easier. For the first layer, there are n possibilites, and then the next layer, there is n-1 combinations.
class Solution { public: vector<vector<int>> combine(int n, int k) { //k numbers vector<vector<int>> ans; vector<int> curr; //in the range of 1 to n dfs(ans, curr, 1, k, n); return ans; } void dfs(vector<vector<int>>&ans, vector<int>&curr, int s, int k, int n){ int currsize = curr.size(); if(currsize==k){ ans.push_back(curr); //do not go to a further depth return; } for(int i=s;i<=n;i++){ curr.push_back(i); dfs(ans, curr, i+1, k, n); curr.pop_back(); } return; } };
78. Subsets
This is also comparatively easy and we can use the similar ideas to solve this questions. The difference is that is stores the results into the ans for every possibilities. For previous quesitons, it stores the value only when it satisfies specific constraints. This one is more generous without specific constraints.
classSolution { public: vector<vector<int>> subsets(vector<int>& nums) { //the number in sets can be 1 to n sort(nums.begin(),nums.end()); vector<int> cur; vector<vector<int>> ans; ans.push_back({}); dfs(ans, cur, nums, 0); return ans; } voiddfs(vector<vector<int>>&ans, vector<int>&curr, vector<int>& nums, int s){ for(int i=s;i<nums.size();i++){ curr.push_back(nums[i]); //for each possible results, put into ans ans.push_back(curr); dfs(ans,curr,nums,i+1); curr.pop_back(); } return; } };
90. Subsets II
There are some difference, it contains the repeated elements in queue, and results should not be repeative. We can solve this using the similar techniques used in 40
classSolution { public: vector<vector<int>> subsetsWithDup(vector<int>& nums) { //the number in sets can be 1 to n sort(nums.begin(),nums.end()); vector<int> cur; vector<vector<int>> ans; ans.push_back({}); dfs(ans, cur, nums, 0); return ans; } voiddfs(vector<vector<int>>&ans, vector<int>&curr, vector<int>& nums, int s){ for(int i=s;i<nums.size();i++){ if(i>s && nums[i]==nums[i-1]){ continue; } curr.push_back(nums[i]); //for each possible results, put into ans ans.push_back(curr); dfs(ans,curr,nums,i+1); curr.pop_back(); } return; } };
216. Combination Sum III
There are not much differences compred with previous type, we put the curr into the ans when the constraints are satisfied.
classSolution { public: vector<vector<int>> combinationSum3(int k, int n) { //n is the targeted value //k represents the list from 1 to k vector<vector<int>> ans; vector<int> curr; dfs(ans, curr, 1, k, n); return ans; } voiddfs(vector<vector<int>>& ans,vector<int>& curr, int s, int k, int target){ if(target==0 && curr.size()==k){ ans.push_back(curr); return; } for(int i=s;i<=9;i++){ int targetnew = target-i; if(targetnew<0){ //do not further go through along this path continue; } //for case targetnew >0 or ==0 using dfs //we list the return point at the begining of the dfs //it can simplify the code a little bit compared with //processing every if condition separately curr.push_back(i); dfs(ans,curr,i+1,k,targetnew); curr.pop_back(); } return; } };
22. Generate Parentheses
Evey node can be the left or right parentheses, and then we trim some results. From the top to bottom, the final path from the root to the leaf node is the actual ans we need to record. We can only place the right parathesis if the count of the left parathesis is larger than 0.
classSolution { public: int totalLen=0; vector<string> generateParenthesis(int n){ vector<string> ans; totalLen=n*2; helper(ans, "", 0); return ans; } voidhelper(vector<string>& ans, string str, int leftc){ int strlen = str.length(); if(strlen == totalLen && leftc==0){ //put string into ans ans.push_back(str); return; } if(strlen<totalLen){ //can put leftc anyway, left child helper(ans,str+"(",leftc+1); if(leftc>0){ // can put right if there is remaining leftc // left child helper(ans,str+")",leftc-1); } } return; } };
37. Sudoku Solver
the idea of checking the conflicts is just check it from the 1-9 and keep calling the next level, try to set the cell to a dot if there is no possible results. return the true if all cells are filled in.
The logic is not complex but it sill take me some time to figure it out. Originally we did not add return true or false, so it basically search all possibilities even if we find a valid results. The idea here is that we return it immediately if we find a valid ans. For the case when there is number at a specific position, we also need to add the return true or false.
classSolution { public: // assume i and j is less then 9 // assume value is from 1 to 9 // the current one is . // make sure what are possible options for specific set vector<int> getOptions(int row, int column, vector<vector<char>>& board){ int boardDim = 9; vector<bool> flag(10, true); // filter row i for (int j = 0; j < boardDim; j++) { if (j == column) continue; if (board[row][j] == '.') { continue; } // filter the conflict value flag[board[row][j] - '0'] = false; }
// filter column j for (int i = 0; i < boardDim; i++) { if (i == row) continue; if (board[i][column] == '.') { continue; } // filter out the conflict one flag[board[i][column] - '0'] = false; }
// filter box int rowBox = row / 3; int columnBox = column / 3;
for (int i = rowBox * 3; i < (rowBox + 1) * 3; i++) { for (int j = columnBox * 3; j < (columnBox + 1) * 3; j++) { if (i == row && j == column) continue; if (board[i][j] == '.') continue; flag[board[i][j] - '0'] = false; } }
// get option vector<int> ans; for (int i = 1; i <= 9; i++) { if (flag[i]) { ans.push_back(i); } } return ans; }
voidsolveSudoku(vector<vector<char>>& board){ // using recursion based dfs dfs(0, 0, board); return; }
booldfs(int row, int column, vector<vector<char>>& board){ int boardRow = 9; int boadColumn = 9;
if (row == boardRow) { returntrue; }
int nextRow = row; if (column == (boadColumn - 1)) { nextRow = row + 1; } int nextColumn = (column + 1) % boadColumn; if (board[row][column] >= '1' && board[row][column] <= '9') { returndfs(nextRow, nextColumn, board); } else { // current value node exist // get options vector<int> options = getOptions(row, column, board); if (options.size() == 0) { // current is conflict returnfalse; } // range options for (int i = 0; i < options.size(); i++) { board[row][column] = options[i] + '0'; bool find = dfs(nextRow, nextColumn, board); if (find==true) returntrue; // pop back (not necessary, there is valid answer anyway) board[row][column] = '.'; } } returnfalse; } };
51. N-Queens
I got this question in one interview, it is comparatively easy to come up with a solution but it is not easy to make it right. When checking the conflicts, I remember to check the row, the column, the left side diagnal but I forget to check the right side diagonal direaction(not sure why) So it adds more possibilities in the output. Another thing is that I try to set the value of status matrix as 0 after each time we found a new solution (which is incorrect and may introduce a lot of empty output). Since the code is recursive way, so it is possible that the last several position is different but the start position is same. If we set the status as the empty, it will also remove the previous status position, which introduce error. This is the version I write in the interview. Which is easy to understand but can be improved further (the process to decide the conflict is a little bit redoundant here).
voidhelper(int remain, int &n, vector<vector<int> >& status, vector<string>& output){ //exit if(remain==0){ //change status to output string outputStr = ToOutput(n, status); //save answer output.push_back(outputStr); //clear status //status.clear(); return; } //where can we place queen //status[remain][0]-status[remian][n-1] bool setq=false; for(int j=0;j<n;j++){ //check conflicts bool ifconflict=checkConflict(n-remain,j, status, n); if(ifconflict){ continue; }else{ //put current queen status[n-remain][j]=1; //continue recursion setq=true; helper(remain-1,n,status,output); //set back status status[n-remain][j]=0; } } if (setq==false){ return; } }
intmain() { //given n return all solutions //testing int n=4; vector<vector<int>> status(n, vector<int>(n,0)); vector<string> output; //void helper(int remain, int &n, vector<vector<int>>& status, vector<string>& output){ helper(n,n,status,output); //checking results for(int i=0;i<output.size();i++){ std::cout <<output[i]<<std::endl; } }
This question is similar to previous one. The dfs need to go thrrough all possible combinations and store the valid results during the traverse. For each level, we can assume the possible options (namely the elements in the set) is the position for each one in different column. Then we use a function to decide if each position is conflict with the current grid results to decide if the current tree can move one step further. The recursion depth is the size of the grid.
Fur the current code, the meaning of each node means if the tree is at the specific row, column position. Since each row can only put one element, so we can simply use a for loop to detect each case and range it. (Every option is exclusive)
Origianlly, we consider a more general case and consider each cell separately. Each cell can put a queue or not, for that code, even though it can work, but we create too many recursions and the code become slow. The time complexity is O(2^(n*n)) for that case, for the current case, the time complexity is O(n*n).
classSolution { public: int m_gridDim; vector<vector<string>> m_ans; vector<vector<int>> dir = {{-1,1},{1,1},{-1,-1},{1,-1}}; vector<vector<string>> solveNQueens(int n) { vector<string> initGrid(n); m_gridDim = n; // init grid for (int i = 0; i < m_gridDim; i++) { for (int j = 0; j < n; j++) { initGrid[j] += "."; } }
dfs(n, 0, initGrid); return m_ans; }
//each row is a new level of the tree boolconflict(int row, int column, vector<string>& grid){
// edge case if (m_gridDim == 1) { returnfalse; }
// check row if (grid[row].find("Q") != string::npos) { // there is Q in this row returntrue; }
// check column for (int i = 0; i < m_gridDim; i++) { if (grid[i][column] == 'Q') { returntrue; } } //check for dir for(int i=0;i<4;i++){ int nextr = row+dir[i][0]; int nextc = column+dir[i][1]; //if the results is in the boundry while (nextr >= 0 && nextr < m_gridDim && nextc >= 0 && nextc < m_gridDim) { if (grid[nextr][nextc] == 'Q') { returntrue; } //continue move nextr=nextr+dir[i][0]; nextc = nextc+dir[i][1]; } } returnfalse; }
// put one queue for one row voiddfs(int remain, int curRow, vector<string>& currGrid){ //printf("r %d\n", curRow); //for (int i = 0; i < m_gridDim; i++) { // printf("%s\n", currGrid[i].c_str()); //} //printf("\n---\n"); if (curRow == m_gridDim) { // out of bound // the current ans might ok if (remain == 0) { m_ans.push_back(currGrid); } return; }
for(int c=0;c<m_gridDim;c++){ //if put at the current row and c bool ifconflict = conflict(curRow, c, currGrid); if(ifconflict){ //can not put at the current position continue; } //put it at the current position currGrid[curRow][c] = 'Q'; dfs(remain - 1, curRow+1, currGrid); // set status back currGrid[curRow][c] = '.'; } return; } };
52. N-Queens II
The idea is similar with previous one, just change the ans when get the valid solution each time.
classSolution { public: int m_gridDim; int m_ans=0; vector<vector<int>> dir = {{-1,1},{1,1},{-1,-1},{1,-1}}; inttotalNQueens(int n){ vector<string> initGrid(n); m_gridDim = n; // init grid for (int i = 0; i < m_gridDim; i++) { for (int j = 0; j < n; j++) { initGrid[j] += "."; } }
dfs(n, 0, initGrid); return m_ans; }
//each row is a new level of the tree boolconflict(int row, int column, vector<string>& grid){
// edge case if (m_gridDim == 1) { returnfalse; }
// check row if (grid[row].find("Q") != string::npos) { // there is Q in this row returntrue; }
// check column for (int i = 0; i < m_gridDim; i++) { if (grid[i][column] == 'Q') { returntrue; } } //check for dir for(int i=0;i<4;i++){ int nextr = row+dir[i][0]; int nextc = column+dir[i][1]; //if the results is in the boundry while (nextr >= 0 && nextr < m_gridDim && nextc >= 0 && nextc < m_gridDim) { if (grid[nextr][nextc] == 'Q') { returntrue; } //continue move nextr=nextr+dir[i][0]; nextc = nextc+dir[i][1]; } } returnfalse; }
// put one queue for one row voiddfs(int remain, int curRow, vector<string>& currGrid){ //printf("r %d\n", curRow); //for (int i = 0; i < m_gridDim; i++) { // printf("%s\n", currGrid[i].c_str()); //} //printf("\n---\n"); if (curRow == m_gridDim) { // out of bound // the current ans might ok if (remain == 0) { m_ans++; } return; }
for(int c=0;c<m_gridDim;c++){ //if put at the current row and c bool ifconflict = conflict(curRow, c, currGrid); if(ifconflict){ //can not put at the current position continue; } //put it at the current position currGrid[curRow][c] = 'Q'; dfs(remain - 1, curRow+1, currGrid); // set status back currGrid[curRow][c] = '.'; } return; } };
The 52 can also be improved based on DP, we do not discuss it details here.
one optimization for 51 and 52 is to do the conflict checking, we may use more memory space and store if there are elements at specific row, column and dialogue to save the speed for checking the conflicts.
For example, statesRow[i] represents if there are queues at ith row, statesColumn[i] represents if there are elements at ith column, similarly for diagonalLeft and diagonalRight.
For the right side diagonal, the sum of the row and column is a fixed number For the left side diagonal, the sum of the column - row is a fixed number We can map the row and column to these two index.
The subsequent code shows how to use this optimization. We also do not need to store the grid explicitly in this way. The framework is similar with previous one and the operation for detecting the conflicts improves a lot. We just memorize the status based on several arrays explicitly.
classSolution { public: int m_gridDim; int m_ans=0;
//each row is a new level of the tree boolconflict(int row, int column){ if (m_gridDim == 1) { returnfalse; }
// check row if (m_rExist[row]) { // there is Q in this row returntrue; }
// check column if (m_cExist[column]) { returntrue; }
// check right diagonal if (m_drExist[row + column]) { returntrue; }
// check left diagonal int leftIndex = column - row + m_gridDim - 1; if (m_dlExist[leftIndex]) { returntrue; } returnfalse; }
// put one queue for one row voiddfs(int remain, int curRow){ if (curRow == m_gridDim) { // out of bound // the current ans might ok if (remain == 0) { m_ans++; } return; }
for(int c=0;c<m_gridDim;c++){ //if put at the current row and c bool ifconflict = conflict(curRow, c); if(ifconflict){ //can not put at the current position continue; } //put it at the current position //set the current status m_rExist[curRow] = 1; m_cExist[c] = 1; m_drExist[curRow + c] = 1; m_dlExist[c - curRow + m_gridDim - 1] = 1; dfs(remain - 1, curRow+1); // set status back m_rExist[curRow] = 0; m_cExist[c] = 0; m_drExist[curRow + c] = 0; m_dlExist[c - curRow + m_gridDim - 1] = 0; } return; } };
Naive DFS-UpToBottom-Permutation
46. Permutations
Typical permutation question, we can reuse the similar framework and put things into the ans only when all elements are checked. Still go through the path as previous one, put the path into the ans only when it get to the end.
Maybe there are more efficient way to consider which path is unnecessary, in this example, we just check if the particular elements is in the curr, if it is already in the curr, we do not go through along that path. The start position in this question start from the 0 to end instead of customized start position to end (since the results can be any order).
We can use another flag vector to label if the element is used or not, if then when we pop the element out, we set the specific label into false. This can further improve the code a little bit.
classSolution { public: vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>> ans; vector<int> curr; dfs(ans,curr,nums); return ans; } boolexist(int k, vector<int>&curr){ for(auto v:curr){ if(v==k){ returntrue; } } returnfalse; } voiddfs(vector<vector<int>>&ans, vector<int>&curr,vector<int>& nums){ if(curr.size()==nums.size()){ ans.push_back(curr); return; } for(int i=0;i<nums.size();i++){ //if i is in the curr //do not go through along this path if(exist(nums[i],curr)){ continue; } curr.push_back(nums[i]); dfs(ans,curr,nums); curr.pop_back(); } return; } };
This is the code with the visited flag (recomended version, we do not need to check existance each time). It looks that the permutation related problem use the visited flag a lot (each ans is a complete path) and the combination problems use the sort a lot (the answer can be half of the path).
classSolution { public: vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>> ans; vector<int> curr; vector<bool> visited(nums.size(),false); dfs(ans,curr,nums,visited); return ans; } voiddfs(vector<vector<int>>&ans, vector<int>&curr,vector<int>& nums, vector<bool>&visited){ if(curr.size()==nums.size()){ //put current path into the ans ans.push_back(curr); return; } for(int i=0;i<nums.size();i++){ //if i is in the curr //do not go through along this path if(visited[i]){ continue; } curr.push_back(nums[i]); visited[i]=true; dfs(ans,curr,nums,visited); //set status back curr.pop_back(); visited[i]=false; } return; } };
47. Permutations II
Similar to the previous question, the input of this problem contains the repeated elements. In previous one, we solve this issue by sorting the input firstly and then compares nums[i] and nums[i-1], when they appears at the second time, we do not go through along that path. It use both the sorting strategy and the visited flag to trim the path
classSolution { public: vector<vector<int>> permuteUnique(vector<int>& nums) { vector<vector<int>> ans; vector<int> curr; vector<bool> label(nums.size(),false); sort(nums.begin(),nums.end()); dfs(ans,curr,nums,label); return ans; } voiddfs(vector<vector<int>>&ans, vector<int>&curr,vector<int>& nums, vector<bool>& label){ if(curr.size()==nums.size()){ ans.push_back(curr); return; } for(int i=0;i<nums.size();i++){ //if i is in the curr //do not go through along this path if(label[i]){ continue; } //only in the current layer //if the previous same one is visited //we do not visit current one if(i>0 && nums[i]==nums[i-1] && label[i-1]==true){ continue; } curr.push_back(nums[i]); label[i]=true; dfs(ans,curr,nums,label); curr.pop_back(); label[i]=false; } return; } };
943. Find the Shortest Superstring
The original idea of this question is that, do all the permulations, and then remove the potential overlapping part.
The original idea to remove the overlapping part is to find if the start position of second string is in the first string. Assuming in the position i of the first string, then compare the i to the end, to see if it appears in the second string, it is possible there are multiple positions. This operation can be applied every time we add a new string.
this operation can be also done before searching (this is a good point), and we store the results explicitly. then we do not need to do the similar operation during the search (we store the information beforehand) This info is important to construct the final path, dfs call is n! for every node, we call n nodes.
//this is the naive search solution //did not pass all the tests, time limit issue //56 / 83 test cases passed.
classSolution { public: intoverlappingLen2(string& first, string& second){ int ans = 0; int upperBound = min(first.length(), second.length()); for (int k = 1; k <= upperBound; k++) { if (first.substr(first.length() - k) == second.substr(0, k)) { ans = max(ans, k); } } return ans; } string shortestSuperstring(vector<string>& words){ string ans; vector<bool> labelUsed(words.size(), false); int wordsLen = words.size(); dfs(words,wordsLen,"",ans,labelUsed,0); return ans; } //we use the parent Str to remember last steps results voiddfs(vector<string>& words, int& wordsSize, string parentStr, string& ans, vector<bool>& labelUsed, int count){ //check all the possible of strings here if(count==wordsSize){ //update ans when all string is counted if(ans.length()==0 || (parentStr.length()<ans.length())){ ans = parentStr; } return; } for(int i=0;i<wordsSize;i++){ if(labelUsed[i]==true){ continue; } int overlapLen = overlappingLen2(parentStr,words[i]); string currStr = parentStr+words[i].substr(overlapLen); labelUsed[i]=true; //dfs check dfs(words,wordsSize,currStr,ans,labelUsed,count+1); //udpate status of the current layer labelUsed[i]=false; } return; } };
This is the version that computes the prior information about the overlap length between each two pairs.
classSolution { public: //use shared part for the ans vector<vector<int>> m_priorInfo; vector<int> m_bestPath; int m_bestLen; intoverlappingLen(string& first, string& second){ int ans = 0; int upperBound = min(first.length(), second.length()); for (int k = 1; k <= upperBound; k++) { if (first.substr(first.length() - k) == second.substr(0, k)) { ans = max(ans, k); } } return ans; } string shortestSuperstring(vector<string>& words){ int wordsLen = words.size(); m_priorInfo =vector<vector<int>> (wordsLen, vector<int>(wordsLen,0)); //process the prior info for(int i=0;i<wordsLen;i++){ for(int j=0;j<wordsLen;j++){ if(i==j){ m_priorInfo[i][j]=words[i].length(); }else{ m_priorInfo[i][j]=overlappingLen(words[i],words[j]); } //printf("info i %d j %d len %d\n",i,j,priorInfo[i][j]); } } vector<bool> labelUsed(words.size(), false); vector<int> currPath; //do the dfs dfs(words,wordsLen,labelUsed,0,0,currPath); //recover the string from the bestPath string ans; for(int i=0;i<m_bestPath.size();i++){ //printf("path i %d %d\n",i,m_bestPath[i]); int currIndex = m_bestPath[i]; if(i==0){ ans+=words[currIndex]; }else{ int lastIndex = m_bestPath[i-1]; ans+=words[currIndex].substr(m_priorInfo[lastIndex][currIndex]); } } return ans; } //we use the parent Str to remember last steps results voiddfs(vector<string>& words, int& wordsSize, vector<bool>& labelUsed, int count, int currLen, vector<int>& currPath){ //check all the possible of strings here if(m_bestLen>0 && currLen>=m_bestLen){ return; } if(count==wordsSize){ //update best path and best len m_bestLen=currLen; m_bestPath=currPath; return; } for(int i=0;i<wordsSize;i++){ if(labelUsed[i]==true){ continue; } int currLenNew = currLen; if(currPath.size()==0){ //the first one currLenNew=words[i].length(); }else{ int overlapLen = m_priorInfo[currPath.back()][i]; //overlappingLen2(words[currPath.back()],words[i]); currLenNew = currLen+(words[i].length()-overlapLen); }
currPath.push_back(i); //string currStr = parentStr+words[i].substr(overlapLen); labelUsed[i]=true; //dfs check dfs(words,wordsSize,labelUsed, count+1, currLenNew, currPath); //udpate status of the current layer labelUsed[i]=false; currPath.pop_back(); //make sure currLen do not change //after each iteration in the for loop } return; } };
This code can not pass all tests because and exceeds the limited time. The ideal way is still to view the problem as a weighted graph and find the shortest path. Refer to the graph listed in huahua’s blog and the official solution here. Using the mask to remember the existing visited nodes is a little bit tricky. The 1 or 0 in each bit position of the mask represents that if the associated value is visited or not. The mask ^ (1<<j) represents that we set jth position as 1 and put it into the mask. (The ^ is the xor opertaion, if the original bit is 0 and current one 1<<j is 1, the results here for specific bit is 1). Using s & (1 << j) operation can check if the specific bit is set. If it is set, the results is a non zero number, otherwise, the result is zero. We do not discuss the dp solution here. The dp solution can be written into the recursive way or not. The core ideas is that we keeping the intermidiate status during the search. How to memorise that information is key point to improve the speed.
996. Number of Squareful Arrays
This is a permutation operation pluse the constraint. The idea is a little bit similar with previous one. Same to the previous one, the naive searching method is still time consuming and the dp method can improve the code a lot, but it is not easy to figure out that dp solution. There are several small points, for example, 0 is also a square number. We can also sort the array and compute the prefix sum to see if the results is squere number. We can avoid the repeated solutions by this way.
classSolution { public: vector<vector<bool>> m_priorInfo; boolsquareNum(int num){ for(int i=0;i*i<=num;i++){ if(i*i==num){ returntrue; } } returnfalse; } intnumSquarefulPerms(vector<int>& nums){ int numSize = nums.size(); m_priorInfo = vector<vector<bool>> (numSize,vector<bool>(numSize,false)); sort(nums.begin(), nums.end()); //do the search int ans=0; vector<int> path; vector<bool> labels(numSize, false); dfs(ans,nums,labels,path); return ans; } voiddfs(int& ans, vector<int>& nums, vector<bool>& labels, vector<int>& path){ //check the results //if valid //how to remove the repeated one? if(path.size() == nums.size()){ ans++; return; } //we need to start from the 0 since we need to go through //all permutations for(int i=0;i<nums.size();i++){ if(labels[i]==true) continue; if(i>0 && nums[i]==nums[i-1] && labels[i-1]==true) continue; if(!path.empty() && !squareNum(path.back()+nums[i])) continue; //all situation need to put the elements path.push_back(nums[i]); labels[i]=true; //dfs for children layers dfs(ans,nums,labels,path); //back to current layer labels[i]=false; path.pop_back(); } } };
This is the version to utilize the prior knoledge, maybe the good strategy is not to compute them all at once, we can cache them during the searching process.
classSolution { public: boolsquareNum(int num){ int s = sqrt(num); return s * s == num; } intnumSquarefulPerms(vector<int>& nums){ int numSize = nums.size(); sort(nums.begin(), nums.end()); //do the search int ans=0; vector<int> path; vector<int> labels(numSize, 0); dfs(ans,nums,labels,path); return ans; } voiddfs(int& ans, vector<int>& nums, vector<int>& labels, vector<int>& path){ //check the results //if valid //how to remove the repeated one? if(path.size() == nums.size()){ ans++; return; } //we need to start from the 0 since we need to go through //all permutations for(int i=0;i<nums.size();i++){ if(labels[i]) continue; //be carefule here //if there are multiple same elements //only the first can be used in the same level, the third one is important //only when the labels for previous one is 0 //we can make sure its dfs complete //otherwise, it might be the condition during the dfs process if(i>0 && nums[i]==nums[i-1] && labels[i-1]==0) continue; if(!path.empty() && !squareNum(path.back()+nums[i])) continue; //all situation need to put the elements path.push_back(nums[i]); labels[i]=1; //dfs for children layers dfs(ans,nums,labels,path); //back to current layer labels[i]=0; path.pop_back(); } } };
The efficient way is still to use the dp method, it is ensentially a hamitonion path in the graphy theory, refer to this explanation (https://www.youtube.com/watch?v=ISnktonx7rY). When there two numbers are prefect squre, there is a path between them.
Naive DFS-UpToBottom-Expression
This type of question provide a expression, then maybe we need to compute some properties according to the expression. There usually exist the inserted structure which can be abstracted into a tree. The question in this type is a little bit like decoding the string into a tree structure with layered information, even if we do not use an actually tree structure, we still need to keep a layer variable to trace current part is at which layer. The 856 is a good example.
856 Score of Parentheses
the code looks super easy we do not even write it into a recursion way, but it is not straightforward to figure out why it works. The whole idea for solving this problem is to emulate a tree structure, different with the previous one, every node is a () pair.
For example, if the input is (()), the imaginary tree is as follows:
() | ()
If there is (()()), the imaginary tree (or the decision tree) is as follows:
() | \ () ()
The key is that we do not consider the implementaion, we consider the abstraction first. Then according to the rule of the score, for each leaf node, its score is 2^depth, then we accumulate all the scores of leaf node together. Although the description of the question is to compute the score from the bottom to top, it is much easier to compute scores from the top to the bottom.
Regarding to the implementation, when there is (, the depth increase, when there is ) the depth decrease, and if the previous one is (, we assume that we met the leaf node. The whole sequence is just like the LRN traversal of the tree
class Solution { public: int scoreOfParentheses(string s) { int score =0; int len = s.length(); int depth=0; //range s for(int i=0;i<len;i++){ if(s[i] == '('){ depth++; }else if(s[i] == ')'){ if(i>0 && s[i-1]=='('){ score+=pow(2,depth-1); } depth--; } } return score; } };
Another way is to find the balanced outlayer strcutre, and then use the recursion to call the inner layer, which is like the tree taversal from the top to the bottom, in the string case, it can use the left and right index to label the each layer of the structure, when you find each layer, the tree depth increase one.
Enssentially, it like the process of decoding the string into the tree and then compute some properties of the tree. For the 394. Decode String, this idea is more obvious, and we basically use the bottom to up strategy of the tree based approach and we decode each subtree recursively. For each level, we just need a function to let it return the reuslts of the subtree. For the tree structure in logically, the leaf node is the character and the parent node is the number. The issue is that in the string structure, we basically flatten everything and not knwo when it end. So that’s why we also return a right index. That right index labels when the current level moves to the end. And then we start from the next segment (which is the node at the same level with the current node)
726. Number of Atoms
This is the a hard one, the main reason is that the rules are a liitle bit complex. The idea is same with previous one, the different place is that we read the string from right side to the left side, it might be easier to consider things in this way. By this way, we check the number first (the non leaf node) then the atom (the leaf node). The code can be further optimized. Although current code can work, it is still a little bit unclear for when to put the information into the map.
classSolution { public: map <string, int> atomMap; string countOfAtoms(string formula){ // ordered map to store the atom and its number string str; int len = formula.length(); int lindex=0; helper(formula,lindex,len-1,len,1); //output the value from map into string for(auto it : atomMap){ string key = it.first; //std::cout << "key" << key <<std::endl; int value = it.second; str+=key; if(value!=1){ str+=to_string(value); } } return str; } //paras: formular, start position, len of the formula //read it from right to left for simplicity voidhelper(string& f, int& lindex, int rindex, int& len, int multiplier){ string atomName; int fNum=1; int i=rindex; while(i>=0){ //std::cout << "i " << i << std::endl; //number if(f[i] >= '0' && f[i]<='9'){ // H2O case, it can be a new started atom if(i+1<len && f[i+1]>='A' && f[i+1]<='Z'){ //this condition is prior than case where there is ( //when this executed, we do not check ( further //this is a new atom //std::cout<<"anmed "<<atomName << "fnum " << fNum << "multi " << multiplier<<std::endl; atomMap[atomName]+=fNum*multiplier; //reset key variables atomName=""; fNum=1; } //current number int tempNum = f[i]-'0'; //read from right to left if(i+1 < len && f[i+1] >= '0' && f[i+1]<='9'){ fNum = tempNum*10+fNum; }else{ fNum = tempNum; }
i--; continue; } //character(multiple) if((f[i]>='A' && f[i]<='Z') || (f[i]>='a' && f[i]<='z')){ //reset the fNum if there are two upper case //the 1 is omitted in expression //also update in this case if(i+1<len && f[i+1]>='A' && f[i+1]<='Z'){ //this condition is prior than case where there is ( //when this executed, we do not check ( further //this is a new atom //std::cout<<"anmec "<<atomName<<std::endl; atomMap[atomName]+=fNum*multiplier; //reset key variables atomName=f[i]; fNum=1; }else{ atomName=f[i]+atomName; } i--; continue; } if(f[i]==')'){ //recursion, process multiple elements inserted //in current section //update l index helper(f, lindex, i-1, len, multiplier*fNum); //remember to set new fNum, from this point, it is a new segment fNum=1; i=lindex-1; continue; } // can start with chracter // when i==0 also insert if(f[i]=='(' || i==0){ //return point //put thing into map //std::cout<<"anmeb "<<atomName<<std::endl; if(atomName!=""){ atomMap[atomName]+=fNum*multiplier; } //reset key variables atomName=""; fNum=1; lindex=i--; return; } } //process the first one if(atomName!=""){ //std::cout<<"anmea "<<atomName<< " fNum " << fNum << " multi " << multiplier << std::endl; atomMap[atomName]+=fNum*multiplier; } } };
Another example is 736, which is a little bit complex. (we will solve it in future)
301. Remove Invalid Parentheses
For this type of question, we need to generate new expression based on given expression. The naive way is to use the binaray tree, if the results increase the specific character or not. Without the trim, the complexity is 2^n, every time we map the status array into a new case.
classSolution { private: set<string> m_ans; int minUpdated = INT_MAX; string inputStr; public: boolvalid(string s){ int depth=0; for(int i=0;i<s.length();i++){ if(s[i]=='('){ depth++; }elseif(s[i]==')'){ depth--; } //do nothing for the letter if(depth<0){ //there are extra right parenthesis returnfalse; } } //if the results is 0 all match return depth==0; } vector<string> removeInvalidParentheses(string s){ inputStr = s; vector<int> removedLabel(s.length(), 0); dfs(0,0,removedLabel); vector<string> ansvec; for (auto v:m_ans){ ansvec.push_back(v); } if(ansvec.size()==0){ ansvec.push_back(""); } return ansvec; } string getNewStr(vector<int>& removedLabel){ string ans; for(int i=0;i<inputStr.length();i++){ //keep the string where there is false labels if(removedLabel[i]==0){ ans+=inputStr[i]; } } return ans; } voiddfs(int removedNum, int s, vector<int>& removedLabel){ if(s>inputStr.length()){ return; } if(removedNum>minUpdated){ return; } //maybe add a cache here string currStr=getNewStr(removedLabel); //printf("currStr %s label %d %d\n",currStr.c_str(),removedLabel[0],removedLabel[1]); if(removedNum==minUpdated){ if(valid(currStr)){ m_ans.insert(currStr); } }elseif(removedNum<minUpdated){ //removedNum < minUpdated //update resutls if(valid(currStr)){ m_ans.clear(); m_ans.insert(currStr); minUpdated = removedNum; } } //todo reorganize the code, the s position mayber larger than //length in previous section if(s>=inputStr.length()){ return; } //trim cases //if letters if(inputStr[s]!='(' && inputStr[s]!=')'){ removedLabel[s] = false; dfs(removedNum,s+1,removedLabel); }else{ //remove current or not removedLabel[s]=1; //do the dfs, removed current dfs(removedNum+1,s+1,removedLabel); //next is removedLabel[s]=0; char c = inputStr[s]; //skip the repeated elements while(s<inputStr.length() && inputStr[s]==c) s++; //if not take then don't take it until the same char dfs(removedNum,s,removedLabel); } return; } };
This is the version based on the bit mask and the cache, it does not improve the performance a lot, it however slows down the code, not sure the reason. (maybe the cache is not necessary)
classSolution { private: set<string> m_ans; int minUpdated = INT_MAX; string inputStr; map<int, string> cache; // map the mask into the string public: boolvalid(string s){ int depth=0; for(int i=0;i<s.length();i++){ if(s[i]=='('){ depth++; }elseif(s[i]==')'){ depth--; } //do nothing for the letter if(depth<0){ //there are extra right parenthesis returnfalse; } } //if the results is 0 all match return depth==0; } vector<string> removeInvalidParentheses(string s){ inputStr = s; vector<int> removedLabel(s.length(), 0); int mask=0; dfs(0,0,mask); vector<string> ansvec; for (auto v:m_ans){ ansvec.push_back(v); } if(ansvec.size()==0){ ansvec.push_back(""); } return ansvec; } //mask labels the removed part string getNewStr(int mask){ string ans; for(int i=0;i<inputStr.length();i++){ //keep the string where there is false labels if((mask & (1<<i))==0) { //if not labeled as removed //added into the ans ans+=inputStr[i]; } } return ans; }
//void dfs(int removedNum, int s, vector<int>& removedLabel){ voiddfs(int removedNum, int s, int mask){ if(s>inputStr.length()){ return; } if(removedNum>minUpdated){ return; } //maybe add a cache here string currStr; if(cache.count(mask)>0){ currStr=cache[mask]; }else{ currStr=getNewStr(mask); cache[mask]=currStr; } //string currStr=getNewStr(removedLabel); //printf("currStr %s label %d %d\n",currStr.c_str(),removedLabel[0],removedLabel[1]); if(removedNum==minUpdated){ if(valid(currStr)){ m_ans.insert(currStr); } }elseif(removedNum<minUpdated){ //removedNum < minUpdated //update resutls if(valid(currStr)){ m_ans.clear(); m_ans.insert(currStr); minUpdated = removedNum; } } //todo reorganize the code, the s position mayber larger than //length in previous section if(s>=inputStr.length()){ return; } //trim cases //if letters if(inputStr[s]!='(' && inputStr[s]!=')'){ //removedLabel[s] = false; //do not need to set, it is 0 initially mask = (mask & ~(1 << s)); dfs(removedNum,s+1,mask); }else{ //remove current or not //removedLabel[s]=1; mask = (mask | (1<<s)); //do the dfs, removed current dfs(removedNum+1,s+1,mask); //next is //removedLabel[s]=0; mask = (mask & ~(1<<s)); char c = inputStr[s]; //skip the repeated elements while(s<inputStr.length() && inputStr[s]==c) s++; //if not take then don't take it until the same char dfs(removedNum,s,mask); } return; } };
394. Decode String
We write this code into a recursion way, once we got the bracket, we do a recursion call. It actually use the bottom to up way to do the dfs
classSolution { public: string decodeString(string s){ int len = s.length(); string str = getSubstr(s, 0, len, len); return str; } string getSubstr(string& s, int l, int len, int& rindex){ string fullstr; int depth=0; int i=l; int repeat=0;
The naive idea is to go through every cell and use each cell as the start position and then call the dfs, if find a specific path during the call, return the true and do not further do the dfs call. The operation to start the search one by one is a imporatant thinking perspective. We need to confirm the start position anyway.
classSolution { vector<vector<char>> m_board; vector<vector<bool>> m_boardFlag; int m_rowNum; int m_colmNum; string m_word; public: boolexist(vector<vector<char>>& board, string word){ m_board = board; m_word = word; m_rowNum = board.size(); m_colmNum = board[0].size(); m_boardFlag = vector(m_rowNum, vector<bool>(m_colmNum,false)); for(int i=0;i<m_rowNum;i++){ for(int j=0;j<m_colmNum;j++){ if(board[i][j]==word[0]){ //reset the flag m_boardFlag = vector(m_rowNum, vector<bool>(m_colmNum,false)); bool find = dfs(i,j,0); if(find) returntrue; } } } returnfalse; } //start from r c find adjacent sequence match with word booldfs(int r, int c, int windex){ //find the word //return if(windex==m_word.length()){ returntrue; } //get out of the bound, return not found if(r>=m_rowNum || r<0 || c>=m_colmNum || c<0){ returnfalse; } //this cell is visited if(m_boardFlag[r][c]==true){ returnfalse; } //we may start to search word from the scratch for this //check current //windex ++ if current is equal if(m_board[r][c]==m_word[windex]){ //current one equal word index position //check the next windex++; m_boardFlag[r][c] = true; //right bool find = dfs(r,c+1,windex); if(find) returntrue; //left find = dfs(r,c-1,windex); if(find) returntrue; //up find = dfs(r-1,c,windex); if(find) returntrue; //down find = dfs(r+1,c,windex); if(find) returntrue; //set current back, the current position is not ok m_boardFlag[r][c] = false;
//if all direaction fail false returnfalse; }else{ returnfalse; }
} };
It is interesting to ask, if it is ok to use the bfs as a kernel to do the path finding. We can not use the bfs for this question, look at this exmaple:[["A","B","C","E"],["S","F","E","S"],["A","D","E","E"]] "ABCESEEEFS" Since we need to set the label position of the cell to 1 if we put it into the queue, however, in this case, for the correct path, it need to go back to find the node in the higher layer that have been visited. However, these nodes have been visited. So we could not get correct answer anyway. Be careful about using the bfs, it is suitable for the case that there is the abstraction about the shortest path or the distance to the root node. And the node that is visited can not be visited anymore during the path search. If there is a cycle in the graph, it is not suitable to use the bfs.
212. Word Search II
There is time limit excedded issue if we just use the similar ideas compared with previous one, namely reuse the previous code and then add another for loop outside of it, since the list of the words can be really large (3*10^4).
The idea is to use a tire tree to extract the common part of the input list. The direactly using of the tire tree is similar to the auto typing when we search things. The keep point is that we use each edge to represent one of the 26 characters and also label the origianl word (if it exist) at the end of the searching path.
// using the Tire tree // refer to huahua's code for the tire tree // this data structure saves the actual value // and use the path to represents the which character it is classTrieNode{ public: vector<TrieNode*> nodes; // children for this nodes string rawWord; // point to the original word TrieNode():nodes(26), rawWord("") {}; //the edge represents the letter ~TrieNode(){ for(auto node:nodes) delete node; } };
classSolution { public: vector<vector<char>> m_board; vector<vector<bool>> m_boardFlag; set<string> m_ans; int m_rowNum; int m_colNum; vector<string> findWords(vector<vector<char>>& board, vector<string>& words){ //make sure to fully use the trie tree sort(words.begin(),words.end()); TrieNode root; //put words into the tree //construct the tree for(auto word:words){ //check each word //the root should always be the top level, all words should in same level TrieNode* cur = &root; for(char c:word){ //printf("c %c\n",c); //attebtion to this one make sure it is r reference TrieNode*& next = cur->nodes[c-'a']; //if next is empty, there might be repeated letter in word if(next==nullptr) { //printf("new node %c\n",c); next=newTrieNode(); } cur = next; } //if the cur is at the end of tree cur -> rawWord = word; } m_board = board; m_rowNum = board.size(); m_colNum = board[0].size(); m_boardFlag = vector(m_rowNum, vector<bool>(m_colNum,false)); //call the dfs for(int i=0;i<m_rowNum;i++){ for(int j=0;j<m_colNum;j++){ //reset the flag, this is not necessary //m_boardFlag = vector(m_rowNum, vector<bool>(m_colNum,false)); dfs(i,j,&root); } } vector<string> ans; for(auto v:m_ans){ ans.push_back(v); } return ans; } voiddfs(int r, int c, TrieNode* root){ //check the boundry if(r>=m_rowNum || r<0 || c>=m_colNum || c<0 || m_boardFlag[r][c]==true){ return; } //check current node char curr = m_board[r][c]; //choose specific path to get next node TrieNode* next = root->nodes[curr-'a'];
//if the next is nullptr, the trie root does not //contains this character, move to the next //current value not exist in the trie tree, there is not match if(next == nullptr) return; //for the subsequent part, current char //exist in the trie tree //check the current nodes //if at the ends of the words //printf("check word %s\n",next->rawWord.c_str()); if(next->rawWord!=""){ //there is raw word till this stage m_ans.insert(next->rawWord); } //if there is actual word //check the whole trie tree //process the current node m_boardFlag[r][c]=true; //right dfs(r,c+1,next); //left dfs(r,c-1,next); //up dfs(r-1,c,next); //down dfs(r+1,c,next); //set the flag back m_boardFlag[r][c]=false; } };
In the previous code, there is always repeated answer, so we use a set to store the results, the key issue is here next->rawWord=""; If we set the rawWord to empty after visiting it each time, we can save lots of time, this is code that is less than 1000ms
// using the Tire tree // refer to huahua's code for the tire tree // this data structure saves the actual value // and use the path to represents the which character it is classTrieNode{ public: vector<TrieNode*> nodes; // children for this nodes string rawWord; // point to the original word TrieNode():nodes(26), rawWord("") {}; //the edge represents the letter ~TrieNode(){ for(auto node:nodes) delete node; } };
classSolution { public: vector<vector<char>> m_board; vector<vector<bool>> m_boardFlag; vector<string> m_ans; int m_rowNum; int m_colNum; vector<string> findWords(vector<vector<char>>& board, vector<string>& words){ //make sure to fully use the trie tree sort(words.begin(),words.end()); TrieNode root; //put words into the tree //construct the tree for(auto word:words){ //check each word //the root should always be the top level, all words should in same level TrieNode* cur = &root; for(char c:word){ //printf("c %c\n",c); //attebtion to this one make sure it is r reference TrieNode*& next = cur->nodes[c-'a']; //if next is empty, there might be repeated letter in word if(next==nullptr) { //printf("new node %c\n",c); next=newTrieNode(); } cur = next; } //if the cur is at the end of tree cur -> rawWord = word; } m_board = board; m_rowNum = board.size(); m_colNum = board[0].size(); m_boardFlag = vector(m_rowNum, vector<bool>(m_colNum,false)); //call the dfs for(int i=0;i<m_rowNum;i++){ for(int j=0;j<m_colNum;j++){ dfs(i,j,&root); } } return m_ans; } voiddfs(int r, int c, TrieNode* root){ //check the boundry if(r>=m_rowNum || r<0 || c>=m_colNum || c<0 || m_boardFlag[r][c]==true){ return; } //check current node char curr = m_board[r][c]; //choose specific path to get next node TrieNode* next = root->nodes[curr-'a'];
//if the next is nullptr, the trie root does not //contains this character, move to the next //current value not exist in the trie tree, there is not match if(next == nullptr) return; //for the subsequent part, current char //exist in the trie tree //check the current nodes //if at the ends of the words //printf("check word %s\n",next->rawWord.c_str()); if(next->rawWord!=""){ //there is raw word till this stage m_ans.push_back(next->rawWord); next->rawWord=""; } //if there is actual word //check the whole trie tree //process the current node m_boardFlag[r][c]=true; //right dfs(r,c+1,next); //left dfs(r,c-1,next); //up dfs(r-1,c,next); //down dfs(r+1,c,next); //set the flag back m_boardFlag[r][c]=false; } };
DFS Partition
Partition can be viewd as a extend type of combination, for example, the question 77 can be the foundation to solve the 698. There are two ways to construct tree for this type, assuming there is 3 numbers, a1 a2 a3
root | \ a1 null | \ | \ a1a2 a1 a2 null ...
For each layer, we only consider weather ai is operated with previous layer, there are 8 tree nodes, and these 8 tree nodes are all cases.
Another way is to use for loop to construct next layer of the tree, this way is based on question 77, and can save some iterations, which has better speed up than previous one. Assuming the node value is 1 to 4
For each time of dividing the subtree, the principle is the start position, for example, at level 0, the start position can be 1 to 4, then at the second level, of 1, the start position is 2 to 4, each path is the potential combination. And we can record the path during the recursion.
By this way, only node start with a1 comes to the deepest layer. The coding in this style is faster than previous one for question 698.
698 Partition to K Equal Sum Subsets
An version with error in it. We assume there are k possible set, and iterate dfs with k iterations. But this is not a complete case, we miss some combinations.
class Solution { int m_gNum=0; int m_gSum=0; public: bool canPartitionKSubsets(vector<int>& nums, int k) { //nums sum int sum=0; for(int i=0;i<nums.size();i++){ sum+=nums[i]; } //edge cases, not the multipler of k if(sum<k || sum % k!=0){ return false; } //int slot sum m_gSum = sum/k; m_gNum = k; //visited flag sort(nums.rbegin(),nums.rend()); vector<int> visited(nums.size(), 0); vector<int> ansIndex; for(int i=0;i<k;i++){ //for each group //dfs ansIndex.clear(); //input visited for(int j=0;j<visited.size();j++){ std::cout << "visited j " << visited[j] << std::endl; }
bool iffind = dfs2(nums,visited,0,k,0, ansIndex); //label visited elements if (iffind==false){ return false; } //go through ans index, set visited as 1 for (int h=0;h<ansIndex.size();h++){ visited[ansIndex[h]]=1; } } return true; } bool dfs2(vector<int>& nums, vector<int>& visited, int currSum, int k, int nextIndex, vector<int>&ansIndex){ if(currSum==k){ //find out one combination return true; }
if(nextIndex>=nums.size()){ //gose to the last element return false; }
if(visited[nextIndex]==1){ //visited, not add, go to check next one return dfs2(nums,visited,currSum,k,nextIndex+1, ansIndex); }
int nextVal = nums[nextIndex];
//two decisions, add this one //push current ansIndex.push_back(nextIndex); bool leftok = dfs2(nums,visited,currSum+nextVal,k,nextIndex+1,ansIndex); //we return either left or right is true if(leftok){ return true; }else{ ansIndex.pop_back(); //not add current one, not push bool rightok = dfs2(nums,visited,currSum,k,nextIndex+1,ansIndex); if (rightok){ return true; } } //both left and right are false return false; }
An TLE version, for each layer, we need to check all possibilities.In this version, at each iteration, we go through all possible cases. So the next layer contains all elements. (Be careful about this)
class Solution { int m_gNum=0; int m_gSum=0; public: bool canPartitionKSubsets(vector<int>& nums, int k) { //nums sum int sum=0; for(int i=0;i<nums.size();i++){ sum+=nums[i]; } //edge cases, not the multipler of k if(sum<k || sum % k!=0){ return false; } //int slot sum m_gSum = sum/k; m_gNum = k; vector<int>visited(nums.size(),0); //visited flag sort(begin(nums),end(nums),greater<int>());// For avoid extra calculation
return dfs3(nums, visited,0,m_gSum,0,m_gNum); }
bool dfs3(vector<int>& nums, vector<int>& visited, int currSum, int target, int nextIndex, int remainGroup){ if(remainGroup==0){ return true; }
if(nextIndex>=nums.size()) return false; //for all possible values for(int i=nextIndex;i<nums.size(); i++){ if (visited[i] || currSum + nums[i] > target) continue; visited[i]=true; bool oktoadd = dfs3(nums,visited,currSum + nums[i],target,i+1,remainGroup); if(oktoadd) return true; //not ok, do not add current one, try next visited[i]=false; } //not find return false; } };
This is based on the original TLE version using dp approach An DFS version with memorization search based on map and bitmask. The visited array can be the bitmask, which is an integer check this solution.
This blog list associated bitmask operations, using bitmaks is the foundation for memorization since the key in that map is the bitmask of visited flag. The searching time decreases from 2000ms to around 138 after using memorization.
classSolution { int m_gNum=0; int m_gSum=0; public: boolcanPartitionKSubsets(vector<int>& nums, int k){ int sum=0; for(int i=0;i<nums.size();i++){ sum+=nums[i]; } //edge cases, not the multipler of k if(sum<k || sum % k!=0){ returnfalse; } //sort can improve the speed //int slot sum m_gSum = sum/k; m_gNum = k; //visited flag //vector<int> visited(nums.size(), 0); int visited=0; unordered_map<int, int> mem; sort(nums.rbegin(),nums.rend()); returndfs(nums,visited,0,k,0, mem); } booldfs(vector<int>& nums, int& visited, int index, int remain, int currSum, unordered_map<int, int>& mem){ if(remain==0){ returntrue; }
if(mem.count(visited)>0){ return mem[visited]; } //the sequence here is important for recursion things, especially for the last rount iteration if(currSum==m_gSum){ returndfs(nums,visited,0,remain-1,0, mem); } if(index>=nums.size()){ returnfalse; } //if(visited[index]==1){ if(visited&(1<<index)){ //there is issue, if it is visited, maybe it we should continue, just jump this one returndfs(nums, visited, index+1, remain, currSum, mem); } bool found = dfs(nums, visited, index+1, remain, currSum, mem); if(found){ mem[visited]=1; returntrue; } //choose current one int tempSum = currSum+nums[index]; if(tempSum>m_gSum){ //not possible to have targeted one returnfalse; } //visited[index]=1; visited |= (1<<index); found = dfs(nums, visited, index+1, remain, tempSum, mem); if(found) { mem[visited]=1; returntrue; } //visited[index]=0; visited = visited & ~(1 << index); mem[visited]=0; returnfalse; } };
This is another version which has fewer iterations then previous one (a little bit faster than previous one), for each node, we check the dfs for its subsequent operations
classSolution { int m_gNum=0; int m_gSum=0; public: boolcanPartitionKSubsets(vector<int>& nums, int k){ //nums sum int sum=0; for(int i=0;i<nums.size();i++){ sum+=nums[i]; } //edge cases, not the multipler of k if(sum<k || sum % k!=0){ returnfalse; } //int slot sum m_gSum = sum/k; m_gNum = k; //vector<int>visited(nums.size(),0); //visited flag int visited=0; sort(begin(nums),end(nums),greater<int>());// For avoid extra calculation unordered_map<int, int> mem; returndfs3(nums, visited,0,m_gSum,0,m_gNum,mem); }
booldfs3(vector<int>& nums, int& visited, int currSum, int target, int nextIndex, int remainGroup,unordered_map<int, int>& mem){ if(remainGroup==0){ returntrue; } if(mem.count(visited)>0){ return mem[visited]; } if(currSum==target){ returndfs3(nums, visited, 0, target, 0, remainGroup-1,mem); }
if(nextIndex>=nums.size()) returnfalse; //for all possible values for(int i=nextIndex;i<nums.size(); i++){ if ((visited&(1<<i)) || currSum + nums[i] > target) continue; visited |= (1<<i); bool oktoadd = dfs3(nums,visited,currSum + nums[i],target,i+1,remainGroup,mem); if(oktoadd) { returntrue; mem[visited]=1; } //not ok, do not add current one, try next visited = visited & ~(1 << i); } //not find mem[visited]=0; returnfalse; } };
Analysing the time complexity for this question is a little bit tricky. This article is a good analysis.
The time complexity is O(k*2^n) for each element, we need to consider wheather it is included into the tree. However, there are two ways to construct tree, using the for loop in each layer is more efficient.
93 Restore IP Addresses
This is also a partition type, compared with previous one, this one is hard to use the memorization since it requires to store actual results instead of the true of false. The pattern to select next node is tricky, it use the start position and the length of the substr to do it. This should be a typical pattern for the substr related question.
For each substr, since the maximal length is 3, we can have three slots to put the dots. The maximum dot we can insert is four. Be careful about these details to decide the dfs configurations.
The subroutine to validate the substr is also error prone, there are a lot of details need to take care of.
classSolution { public: vector<string> restoreIpAddresses(string s){ //edge cases vector<string> ans; int len = s.length(); if(len<4){ return ans; } //start dfs vector<string> validSubStrs; //init position, the length of current substr, remain substr for(int l=1;l<=3;l++){ validSubStrs.clear(); dfs(0, l, 4, s, validSubStrs, ans); } return ans; } //for a specific substr between two dots //if it is a valid integer boolvalid(string substr){ //length 0 to 3 int len = substr.length(); if(len>3){ returnfalse; } //second position is not 0 if(len>=2 && substr[0]=='0') returnfalse; //does not contain special character int v=0; for(int i=0;i<len;i++){ if(substr[i]<'0' || substr[i]>'9') returnfalse; v=v*10+(substr[i]-'0'); } //from 0 to 255 if(v>255){ returnfalse; } returntrue; } //each node is a integer for specific segment voiddfs(int spos, int subslen, int remain, string& s, vector<string>&validSubStrs, vector<string>&ans){ if(remain<=0){ return; } if((spos+subslen) > s.length()){ //exceeds the limitation return; } //if valid and the remain is 0 //put it into the ans string substr = s.substr(spos,subslen); if(valid(substr)==false){ return; } //current substr is valid //remain value decreases one validSubStrs.push_back(substr); remain--; //if already been zero, do not go to next layer further if(remain==0){ if((spos+subslen) < s.length()){ //not get to the last position even when remain is 0 validSubStrs.pop_back(); return; } //organize validSubStrs into a complete string string ip; for(int i=0;i<validSubStrs.size();i++){ if(i==0){ ip=ip+validSubStrs[i]; continue; } ip=ip+"."+validSubStrs[i]; } ans.push_back(ip); //set status back validSubStrs.pop_back(); return; } //if remain is not zero, and current is valid //call the dfs for several possible cases at the next layer //use len to represent length of next position //for next layer, the maximal is three spots for each substr for(int l=1;l<=3;l++){ dfs(spos+subslen,l,remain,s,validSubStrs,ans); } //subsequent cases based on current one is completed validSubStrs.pop_back(); return; } };
131. Palindrome Partitioning
When moving from current root to children, the rule here is the length of the substr, the len of substr can start from 1 to len-start position of substr. The start position of substr is the 0+len of substr. The approach to construct substr is similar to the prevous IP question. We need a subroutine to decide if a specific substr satisfies a specific condition.
For each layer of the tree, each layer represents one possible solution of the substr. For example, if the input string is aabcb, then the first layer is ‘a’,’aa’,’aab’,’aabc’,’aabcb’. (the start position is 0 and the length of substr is 1 to n) Then we will check subsequent partitions. For example, the ‘aab’ is not a valid solution, so we do not move to the next layer for this tree.
For the option ‘a’, it is a valid one, so we can move to the next layer for this tree. which contains ‘a’,’ab’,’abc’,’abcb’, then we will do similar operations and checkings. The maximal depth of the tree in this pattern is the maximal possibilities to do the partition, which is the length of the string for this question.
Be careful about approach to transfer the substring, we use the whole string, start position, length of the substr to do that. That is conveneint to do since the parameter used by substr API of std::string is start position and str length.
This is assocaited code:
classSolution { public: vector<vector<string>> partition(string s) { //init records vector<vector<string>> solutions; vector<string>curr; dfs(0,curr,solutions,s); return solutions; } voiddfs(int start, vector<string>&curr, vector<vector<string>>& solutions, string& s){ int size = s.size(); if(start == size){ //there is only one element solutions.push_back(curr); return; } for(int len=1;len<=s.length()-start;len++){ //check current string substr = s.substr(start,len); //trim the branch, this partition not work if(isPlin(substr)==false) continue; curr.push_back(substr); //continue to construct the curr solution dfs(start+len,curr,solutions,s); //set back status after each iteration curr.pop_back(); } } boolisPlin(string s){ int size = s.size(); if(size==1){ returntrue; } for(int i=0;i<size/2;i++){ int j = size-1-i; if(s[i]!=s[j]){ returnfalse; } } returntrue; } };
241 Different Ways to Add Parentheses
The first thing is to understand question clearly, the output is a list that contains all possible results of equations.
The tree structure is a little bit different for this one. Each node is supposed to be a expression, but the expression can be divided into three types, the expression such as 2-1-1 the operator such as - or + the node with number, which is the leaf node and can be retured to the root node.
So when we start from root to bottom, assuming the root expression is 2-1-1, then then second layer is - and - which are two operators. For the first node - its two subnodes are 2 and 1-1, then we can call same subroutine one these nodes.
Be careful that the return value is not one sigle vale, it is multiple values, which is a vector, for each time we merge results returned from two subtrees, it is a set operation or cartisian products operation for two reuslts.
The conveneint point for this one is that the node is just an expression, which is ensentially a string, which is easy to be set as a key of the map, so this make the memorization search possible for this question.
classSolution { public: vector<int> diffWaysToCompute(string expression){ vector<int> ans; //edge cases if(expression.length()==0){ return ans; } //memorization search unordered_map<string, vector<int>> cache; ans = dfs(expression,cache); return ans; } intcompute(int a, int b, char op){ if(op=='+'){ return a+b; }elseif(op=='-'){ return a-b; }elseif(op=='*'){ return a*b; }else{ printf("false op %c\n",op); } return0; } //cartision operation to compute the reuslts of two sets with op vector<int> setCompute(vector<int>& lset, vector<int>& rset, char op){ vector<int> ans; for(auto l:lset){ for(auto r:rset){ int v = compute(l,r,op); ans.push_back(v); } } return ans; } boolifleaf(string& exp){ //the value is from 0 to 99 if(exp.length()>2){ returnfalse; } //from the back to front //if there is op return false for(int i=(exp.length()-1);i>=0;i--){ if(exp[i]>='0' && exp[i]<='9'){ continue; }else{ returnfalse; } } returntrue; } vector<int> dfs(string exp, unordered_map<string, vector<int>>&cache){ //hit cache return if(cache.count(exp)>0){ return cache[exp]; } //get to the leaf node, when it contains one number //there is only one possible value, return vector with one elemenet //insert results into cache if(ifleaf(exp)){ int v = stoi(exp); vector<int> currset = {v}; cache[exp]=currset; return currset; } //processing expression and divide it into branches //check all possible op //break down into subtrees vector<int> currset; //the last digit is the number definately //find out the char which is operator, which can be the //point to break the string for(int i=0;i<(exp.length()-1);i++){ if(exp[i]>='0' && exp[i]<='9'){ continue; } //for the op character //get the left exp and right exp char op = exp[i]; //start to current string lexp = exp.substr(0,i); //next to end string rexp = exp.substr(i+1); //get left set and right set vector<int> lset = dfs(lexp,cache); //op the left and right vector<int> rset = dfs(rexp,cache); vector<int> tempset = setCompute(lset,rset,op); //merge tempset into currset currset.insert(currset.end(), tempset.begin(),tempset.end()); //do not need to set back status } //cache the current ans cache[exp]=currset; return currset; } };
282 Expression Add Operators
This question is a hard one, which is a little bit ticky to solve, but when we consider it by dividing is into several samller questions, it start to getting eaiser. This question is a hard one and it is also an inspiring one, the solution to solve it step by step is a good exercise for solving the hard question. This is a both partition and the combination question.
Compared with the 241, we need to compute the results of this question on the fly since we can not use the divide and conqure approach to solve this question, which has the depedency when there is times operation.
1 output all combinations of potential operatands in string
we just need to use the common type of recursion based on for loop, here, we use comma to express an operator, each time, the length of operator can from the current position to the end of the string, the start position of the previous is the next element of the previous operand. At each level of the recursion tree, we fix one operand, and then we store the path of the tree in the fly into an string.
classSolution { public: std::string InputStr; int Target; vector<string> addOperators(string num, int target){ vector<string> ans; InputStr=num; Target=target; dfs(0,0,0,"",ans); return ans; } //index represent the position to extract from inputstr voiddfs(int index, int prevOperand, int currValue, string exp, vector<string>& ans){ //decide if hit the leaf node and need to return if(index==InputStr.size()){ return; } //get operand and process current int currOperand=0; int oprLen=1; for(int i=index;index+oprLen-1<InputStr.size();oprLen++){ currOperand=currOperand*10+(InputStr[index+oprLen-1]-'0'); //for each possible operand std::string expNew = exp; if (index==0){ expNew = expNew+to_string(currOperand); }else{ expNew = expNew+","+to_string(currOperand); } //go to next layer dfs(index+oprLen,prevOperand,currValue,expNew,ans); } } };
2 compute results of all potential operands output in 1 only using + and - 3 only filter out the results that satisfies specific conditions of 2
This is comparatively easy to do based on previous one. Since the + and - is easy to compute on the fly, we do not need to change the value of the previous expression. At the start position of the function, we just return the result when the value equals to specific target. We combine sub-problem 2 and 3 together.
classSolution { public: std::string InputStr; int Target; vector<string> addOperators(string num, int target){ vector<string> ans; InputStr=num; Target=target; dfs(0,0,0,"",ans); return ans; } //index represent the position to extract from inputstr voiddfs(int index, int prevOperand, int currValue, string exp, vector<string>& ans){ //decide if hit the leaf node and need to return if(index==InputStr.size()){ //moves to invalid position if(currValue==Target){ ans.push_back(exp); } return; }
//get operand and process current int currOperand=0; int oprLen=1; for(int i=index;index+oprLen-1<InputStr.size();oprLen++){ currOperand=currOperand*10+(InputStr[index+oprLen-1]-'0'); //std::cout << currOperand << std::endl; //for each possible operand std::string expNew; if (index==0){ expNew = exp+to_string(currOperand); //go to next layer dfs(index+oprLen,prevOperand,currValue+currOperand,expNew,ans); }else{ //+ expNew = exp+"+"+to_string(currOperand); dfs(index+oprLen,prevOperand,currValue+currOperand,expNew,ans); //- expNew = exp+"-"+to_string(currOperand); dfs(index+oprLen,prevOperand,currValue-currOperand,expNew,ans); } } } };
4 expand the type of operators and also consider the operator * based on 3. This one is a little bit tricky, since we need to keep the previous operand when we consider the times operand. For example, if current expression is 1+2, then we get next one *3, we need to update the new value by 3-2+2*3, which means using the current value minus the previous operand and then add the operand times the current operand. So it is important to keep track of the previous operand. For the + and -, the previous operand is just the current one. For the * operation, the new previous operand is operand*currValue, we need to view them as a whole portion.
Also be carefule about zero, for the operator start with 0 but there are more than 2 digits, we need to skip it since it is not a valid operator such as 05
classSolution { public: std::string InputStr; int Target; vector<string> addOperators(string num, int target){ vector<string> ans; InputStr=num; Target=target; dfs(0,0,0,"",ans); return ans; } //index represent the position to extract from inputstr voiddfs(int index, longint prevOperand, longint currValue, string exp, vector<string>& ans){ //decide if hit the leaf node and need to return if(index==InputStr.size()){ //moves to invalid position if(currValue==Target){ ans.push_back(exp); } return; }
//get operand and process current longint currOperand=0; int oprLen=1; for(int i=index;index+oprLen-1<InputStr.size();oprLen++){ //if start with 0 and have two digits, not a valid operand, //such as case 105 if(InputStr[index]=='0' && oprLen>=2){ continue; } currOperand=currOperand*10+(InputStr[index+oprLen-1]-'0'); //std::cout << currOperand << std::endl; //for each possible operand std::string expNew; if (index==0){ expNew = exp+to_string(currOperand); //go to next layer dfs(index+oprLen,currOperand,currValue+currOperand,expNew,ans); }else{ //+ expNew = exp+"+"+to_string(currOperand); dfs(index+oprLen,currOperand,currValue+currOperand,expNew,ans); //- expNew = exp+"-"+to_string(currOperand); dfs(index+oprLen,-currOperand,currValue-currOperand,expNew,ans); //* expNew = exp+"*"+to_string(currOperand); longint newCurrValue = currValue-prevOperand+prevOperand*currOperand; dfs(index+oprLen,prevOperand*currOperand,newCurrValue,expNew,ans); } } } };
5 More optimization. The previous one can make most of results right, but there are some TLE case, the typical memorization is not suitable for this question since we compute the current value on the fly. After checking assocaited answer, I founud that the issue is caused by exra string copy, so I save the extra string and make the code more clean, this is the final version:
classSolution { public: vector<string> addOperators(string num, int target){ vector<string> ans; dfs(0,0,0,"",num,target,ans); return ans; } //index represent the position to extract from inputstr voiddfs(int index, longint prevOperand, longint currValue, string exp, string& num, int&target, vector<string>& ans){ //decide if hit the leaf node and need to return if(index==num.size()){ if(currValue==target){ ans.push_back(exp); } return; } //get operand and process current longint currOperand=0; int oprLen=1; string operandStr; for(int i=index;index+oprLen-1<num.size();oprLen++){ //if start with 0 and have two digits, not a valid operand, //such as case 105 if(num[index]=='0' && oprLen>=2){ continue; } currOperand=currOperand*10+(num[index+oprLen-1]-'0'); operandStr+=num[index+oprLen-1]; //for each possible operand if (index==0){ //go to next layer dfs(index+oprLen,currOperand,currValue+currOperand,exp+operandStr,num,target,ans); }else{ //+ dfs(index+oprLen,currOperand,currValue+currOperand,exp+"+"+operandStr,num,target,ans); //- dfs(index+oprLen,-currOperand,currValue-currOperand,exp+"-"+operandStr,num,target,ans); //* dfs(index+oprLen,prevOperand*currOperand,currValue-prevOperand+prevOperand*currOperand,exp+"*"+operandStr,num,target,ans); } } } };
842. Split Array into Fibonacci Sequence
This solution use the similar pattern of dfs based on partition. For each time of processing the current node, start from the index, and the length of the substr satisfy some constraints.
Be careful about the edge cases for this question such as the upper bound of the number. And the special case to check if the operator is a valid one (the one start with 0 and have more than two digits are invalid, such as 02, 03 are invalid values.)
This one is easy to solve if we can understand the previous one (282)
classSolution { public: vector<int> splitIntoFibonacci(string num){ vector<int> path; //edge case if(num.length()<3){ return path; } dfs(0,num,path); return path; } boolcontinueRec(vector<int>& path){ if(path.size()<3){ //less than three number, continue recursion returntrue; } for(int i=0;i<path.size()-2;i++){ //not valid, do not further recursion if(long(path[i])+long(path[i+1])>INT_MAX){ returnfalse; } if(long(path[i])+long(path[i+1])!=long(path[i+2])){ returnfalse; } } returntrue; } //index=0, the split position is after 0 //return value represents find or not booldfs(int index, string& num, vector<int>& path){ if(continueRec(path)==false){ //this path not valid, do not go further returnfalse; } //if goes to the leaf //the path is also valid if(index>=(num.length()) && path.size()>=3){ returntrue; } //split current string //index to index+len is first, remaining part is second number //return any one is ok for(int len=1;index+len<=num.length();len++){ //process the case that start with zero //the output of 01 is 1 if(num[index]=='0' && len >1) break; //invalid number longint currnum = stol(num.substr(index,len)); if(currnum >= INT_MAX) break; //out of the upper bounud path.push_back(int(currnum));
bool find=dfs(index+len,num,path); if(find==false){ //pop back and continue search path.pop_back(); }else{ //find one, exit, remember to set return label here returntrue; } } returnfalse; } };
BFS with level size and visited flag
The naive BFS is the basic skills, we put node into the queue, and then pop it gradually, at each time we get a new node from the queue, we then process its children. There are two basic tricks based on it.
One is to get the level size, in this case, before pop out the node, we firstly get the size of the queue, this means the number of node in the current layer, then we use another loop with condition levelSize>0, when nodes in one layer are processed completely, we than do some operation such as dist+1. If we do not use this techniques, we need to store the level value into the node, and each time we get a node from the queue, we access that dist or level value.
Another trick is to set the visited flags, for the question to compute the shortest distance, if we do not add the visited flag, it is possibile to get into the infinity loop.
The question 1091 can be viewed as a template question, it uses several practical skills which are commonly in BFS questions, such as move array, levelsize, and visited flag. These subroutine might be used in more complicated questions such as 675.
1091. Shortest Path in Binary Matrix(A template question)
class Solution { public: int shortestPathBinaryMatrix(vector<vector<int>>& grid) { int r = grid.size(); int c = grid[0].size(); //edge cases if(grid[0][0]==1 || grid[r-1][c-1]==1) return -1; if(r==1 && c==1 && grid[0][0]==0) return 1; vector<vector<int>> visited(r,vector<int>(c,0)); vector<vector<int>> move ={{-1,0},{-1,-1},{0,-1},{1,1},{1,0},{1,-1},{0,1},{-1,1}}; queue<pair<int, int>> q; q.push({0,0}); visited[0][0]=1; int dist=1; while(!q.empty()){ //current level size int levelSize = q.size(); while(levelSize>0){ //get node auto node = q.front(); q.pop(); //check children for(int i=0;i<8;i++){ int nr = node.first+move[i][0]; int nc = node.second+move[i][1]; //out of bounuds if(nr<0 || nr >=r || nc <0 || nc >=c ){ continue; } //visited if(visited[nr][nc]==1){ continue; } //no road if(grid[nr][nc]==1){ continue; } //go to the dest if(nr==r-1 && nc==c-1){ return dist+1; }else{ q.push({nr,nc}); //visited visited[nr][nc]=1; } } levelSize--; } //ok for one layer dist++; } //no road return -1; } };
788 The Maze II(Lintcode)
This is basically the same question with the previous one, the only difference is that the src and dest are also the input parameters.
17 Output all possible combinations.
We basically need to output all the paths, each number represents a new level for each all possible nodes. Essentailly, there is a tree structure and it is good to use the bfs method to search all the tree and only put the results in vector at the last layer. We do not need to put the value in ans at the first several layers and we just need to put the value into the ans at the final layer. The code structure is same with the tree based version, the difference is that the node is not the actual tree node, it is just the imaginary tree node.
classSolution { public: vector<string> letterCombinations(string digits){ vector<string> ans; int len = digits.length(); if(len==0){ return ans; } //init dial table map<int,vector<string>> dialMap; dialMap[2]={"a","b","c"}; dialMap[3]={"d","e","f"}; dialMap[4]={"g","h","i"}; dialMap[5]={"j","k","l"}; dialMap[6]={"m","n","o"}; dialMap[7]={"p","q","r","s"}; dialMap[8]={"t","u","v"}; dialMap[9]={"w","x","y","z"}; //init the q queue<string> q; int initkey = digits[0]-'0'; for(auto v:dialMap[initkey]){ if(len>1){ q.push(v); }elseif(len==1){ ans.push_back(v); } } for(int i=1;i<len;i++){ //construct all possible results at current layer int key = digits[i]-'0'; //fetch the value at i-1 layer int qsize = q.size(); while(qsize>0){ string preStr=q.front(); //put new nodes into the queue for(auto v:dialMap[key]){ string currStr = preStr+v; //put value into the q if i<len-1 //put the q value into the ans i ==len-1 if(i<len-1){ q.push(currStr); }elseif(i==(len-1)){ ans.push_back(currStr); } } //pop out old nodes q.pop(); qsize--; } } return ans; } };
784. Letter Case Permutation
This is the sample code, the framework is still same with previous one (dfs split the current string into the current part and the remaning part). We just classifiy the type of each elements can consider each operations gradually. the idea is still the recursion based on dfs manner.
The goal of algorithm is to find all the combinations, for each character which is a letter, it can be either a small case or large case, so there are two options for current layer
classSolution { public: vector<string> letterCasePermutation(string s){ vector<string> ans; string curr; dfs(ans, s, curr, 0); return ans; } voiddfs(vector<string>& ans, string&sample, string curr, int index){ if(index==sample.length()){ //all elements are pushed into the curr ans.push_back(curr); return; } //if not letter, move to next char temp = sample[index]; if(temp>='a' && temp<='z'){ //if letter //dfs results with the change char letterNew = temp-'a' + 'A'; string currLower=curr+temp; string currUpper=curr+letterNew; dfs(ans, sample, currLower, index+1); dfs(ans, sample, currUpper, index+1); }elseif(temp>='A' && temp<='Z'){ char letterNew = temp-'A' + 'a'; string currUpper=curr+temp; string currLower=curr+letterNew; dfs(ans, sample, currLower, index+1); dfs(ans, sample, currUpper, index+1); }else{ //not letter curr=curr+temp; dfs(ans, sample, curr, index+1); } return; } };
126
One key issue here is the defination of the visited flag, how to define it. There are two definations. The first one is that, once the node is checked, we assume it is visited. Another case is that, once the adjacent nodes around current nodes have been checked, we think it is visited.
The 126 is the case that visited nodes is checked out not
c \ a - b
For this case, if a and c are in the queue during the bst search, we then check the b and label b as visited. Then when we pop out the c from the queue, we do not further put the b into the queue, since it has been labeled as visited. In this case, the edge c->b is not checked. The 127 is a simple case for it.
Another case is check the node after the adjacent nodes is checked. In this case, the operation of setting the flag as true after checking all adjacent nodes. We also list the assocaited code in 127. For the 126 question, this is more suitable solution, since for the one critical nodes, it can be the adjacent node of multiple nodes, so we need to make sure every edge is visited.
In summary, if we need only search the shortest path, we can use the first defination, otherwise, if we need to record all possible path, we need to use the second defination about the visit flags.
127. Word Ladder
The shortest is a kind of key word to remind people to use the BFS. Although we can use dfs (maybe easy for programming), but it is easy to extends the time limit in general cases. If we look at the size of the input list, it is really large, so the dfs is easy to create a really deep recurtion tree.
This is the dfs version, for each time, we go through the list and find one wich is one different with the current one (this is time consuming)
classSolution { vector<string> m_wordList; string m_beginWord; string m_endWord; int m_bestPath = INT_MAX; // do not account the start and the end vector<bool> m_flag; public: boolinlist(){ for(auto w:m_wordList){ if(w==m_endWord){ returntrue; } } returnfalse; } intladderLength(string beginWord, string endWord, vector<string>& wordList){ m_wordList = wordList; m_beginWord=beginWord; m_endWord=endWord; m_flag = vector<bool>(m_wordList.size(),false); //make sure the end word is in list bool ifinlist = inlist(); if(ifinlist==false){ return0; } dfs(beginWord,0); if(m_bestPath>0 && m_bestPath!=INT_MAX){ return m_bestPath+1; } return0; } //function compare 1 letter diff booloneDiff(const string& str1, const string& str2){ //can the str1 and str2 in different length int len1 = str1.length(); int len2 = str2.length(); int lenDiff = abs(len1-len2); if(lenDiff>1){ returnfalse; } int diff=0; for(int i=0;i<min(len1,len2);i++){ if(str1[i]!=str2[i]){ diff++; } if(diff>1){ returnfalse; } } if((diff+lenDiff)==1){ returntrue; } returnfalse; } voiddfs(string curr, int currPath){ //if wordsNum>1 //current word is one letter diff with endWord //return true if(currPath>=1 && curr == m_endWord){ m_bestPath = min(m_bestPath,currPath); return; } //check all avaliable words //this can be very large and up to 3000 for(int i=0;i<m_wordList.size();i++){ if(m_flag[i]){ //this word have been used continue; } //word is not used //check if it is one letter diff with current if(oneDiff(curr,m_wordList[i])){ //this one is a potential one m_flag[i]=true; dfs(m_wordList[i],currPath+1); //set flag back after dfs search m_flag[i]=false; } } return; } };
The reason that we need to use the visited flag is because there is a graph in the given data structure, we try to use the visited flag to avoid the repeated visit. This visit flag checking is usually happens at the step when we decide if we put the new nodes into the queue.
There are several small places we need to take care of. The idea of the pattern map, which represents the how we move to the next layer. (This idea comes from this video). We enssentially use this data structure to construct a graph based on the input data. Understanding this idea is very important, we need to have a logical graph firstly (not the tree in this question) and then use bfs to search the distance.
When processing status, one case is that when pushing the element into the queue, we label it as visited, another case is that when extract it from the queue, we label it as visited. If we label it as visited when we put things into the queue, otherwise, there is repeated path, we may take actual jumps between the brother nodes in one layer.
The ++ operation should be put at the position when one layer is finished processing instead of when there is new elements is extracted from the pattern.
classSolution { public: intladderLength(string beginWord, string endWord, vector<string>& wordList){ // check if the endword is in the list bool endExist = false; for (auto v : wordList) { if (v == endWord) { endExist = true; break; } }
if (endExist == false) { // end not exist return0; }
// build the dic (grpah) with the pattern // key is pattern, value is assocaited string // We can use this info to check the adjacent nodes in the graph each time unordered_map<string, set<string>> patternMap; string pattern; wordList.push_back(beginWord); for (auto word : wordList) { for (int i = 0; i < word.length(); i++) { pattern = word; pattern[i] = '*'; patternMap[pattern].insert(word); } }
set<string> visited; visited.insert(beginWord);
// bfs int res = 1; queue<string> q; q.push(beginWord);
while (q.empty() == false) { // visit current layer // for the new layer int qsize = q.size(); while (qsize > 0) { // get current string currw = q.front(); q.pop(); qsize--;
// check all patterns // get to the end
// check words in pattern map for (int i = 0; i < currw.length(); i++) { pattern = currw; pattern[i] = '*'; for (auto pattenw : patternMap[pattern]) { //find the adjactent nodes based on the pattern we extracted if (visited.find(pattenw) == visited.end()) { // not exist // set flag when put things into the queue // if the word haved been used, we do not iterate it further visited.insert(pattenw); q.push(pattenw); if (pattenw == endWord) { // the first finded one is the shortest one // we do not need to iterate all possibilities return res + 1; } } } } } // finsh processing one layer res++; }
// did not get to the res return0; } };
This is the version of the code we set the flag after checking all adjacent nodes. There are some major differences compared with previous version
(1) We do not need to set the root node into the queue before bfs
(2) We check the visited status before the bfs checking
(3) We set the flag after checking the all status of the current nodes, the previous one is to check the flag in the for loop when check each status. we also check the flag here, we insert it only if it is not visited.
classSolution { public: intladderLength(string beginWord, string endWord, vector<string>& wordList){ // check if the endword is in the list bool endExist = false; for (auto v : wordList) { if (v == endWord) { endExist = true; break; } }
if (endExist == false) { // end not exist return0; }
// build the dic with the pattern unordered_map<string, set<string>> patternMap; string pattern; wordList.push_back(beginWord); for (auto word : wordList) { for (int i = 0; i < word.length(); i++) { pattern = word; pattern[i] = '*'; patternMap[pattern].insert(word); } } //only when the nodes are put into the queue, then labeled it as visited set<string> visited;
// bfs int res = 1; queue<string> q; q.push(beginWord);
while (q.empty() == false) { // visit current layer // for the new layer int qsize = q.size(); while (qsize > 0) { // get current string currw = q.front(); q.pop(); qsize--;
//jump the first case if(visited.find(currw) != visited.end()){ //this one is visited continue; }
// check words in pattern map for (int i = 0; i < currw.length(); i++) { pattern = currw; pattern[i] = '*'; for (auto pattenw : patternMap[pattern]) { // not exist // set flag when put things into the queue // if the word haved been used, we do not iterate it further if(pattenw==currw) continue; q.push(pattenw); if (pattenw == endWord) { // the first finded one is the shortest one // we do not need to iterate all possibilities return res + 1; } } } visited.insert(currw); } // finsh processing one layer res++; } // did not get to the res return0; } };
752. Open the Lock
This is the typical bfs + flag question, this will be a typical one and can be solved with the common framework. We use the getAdjacent to get the possible adjacent nodes (2*4 possibilities) at each step. All poissible nodes for next layer are stored in an array.
If the new one is the deadends(constrains giving by the question) or the node that have been visited previously. We do not visit them again.
classSolution { public: vector<string> getAdjacent(string curr, set<string>& visited, set<string>& deadSets){ vector<string> ans; for(int i=0;i<4;i++){ string strnew = curr; //back char back = curr[i]-1; if(curr[i]=='0'){ back = '9'; } strnew[i] = back; //check the deadends if(deadSets.find(strnew) == deadSets.end() && visited.find(strnew) == visited.end()){ //not exist in dead end ans.push_back(strnew); } //forward char next = curr[i]+1; if(curr[i]=='9'){ next = '0'; } strnew[i] = next; //check visited, if visited, do not push into the q if(deadSets.find(strnew) == deadSets.end() && visited.find(strnew) == visited.end()){ //not visited ans.push_back(strnew); } } return ans; } intopenLock(vector<string>& deadends, string target){ int ans = 0; //set to store the dead ends set<string> deadSets(deadends.begin(),deadends.end()); //a flag to label the visited nodes //visit flag only represents if the node is visited or not set<string> visited; //edge cases if(deadSets.find(target)!=deadSets.end() || deadSets.find("0000")!=deadSets.end()){ //if the target or start is in deadSets //could not find anyway return-1; } if(target=="0000"){ return0; } //bfs queue<string> q; q.push("0000"); visited.insert("0000"); //for current nodes while(q.empty()==false){ int qsize = q.size(); while(qsize>0){ //get the front one string curr = q.front(); q.pop(); qsize--; //compute the all possible adjacent nodes //merge the process of getAdjacent and deadSets/visited check //can improve the speed vector<string> adjStrs = getAdjacent(curr, deadSets, visited); for(auto v:adjStrs){ if(v==target){ return ans+1; } //not exist in deadends and not visited visited.insert(v); //not the target, push into the queue //printf("push %s\n",v.c_str()); q.push(v); //parent[v]=curr; }//for all adjacents }//while q size //update ans for each layer ans++; }//while q empty //did not find target return-1; } };
818. Race Car
The bfs part is similar with previous framework, there are two options for each step. The tricky part is the trimming operation. The nodes number is 2^k if we do not do the trimming operation, which make the bfs operation become redoundant quickly. This question also shows another way to use the flag array. We basically code it based on customized way such as pos_speed in this question and put the coded str into the set.
Another strategy for this kind of problem is to use the dp programming. We do not disucss it here, bascially for each position, we need to consider how many possibilities can get to associated position.
//this is an example of customized node //if we do not use the pair, we can define it by this way structNode { Node (int pos, int speed):m_pos(pos),m_speed(speed){}; int m_pos; int m_speed; booloperator <(const Node& obj) const { if ((this->m_pos < obj.m_pos) || (this->m_speed < obj.m_speed)) { returntrue; } else { returnfalse; } } };
classSolution { public: intracecar(int target){ int ans=0;
if(target==0){ return0; } //visited position (still exceeds the limitation) set<string> visited; //serilize the pair visited.insert("0_1");
//bfs //the first of pair is pos //the second of pair is speed queue<pair<int,int>>q; q.push({0,1}); while(q.empty()==false){ //process current layer int qsize = q.size(); while(qsize>0){ auto node = q.front(); q.pop(); qsize--; //check move case //if A move int np = node.first+node.second; int ns = node.second*2; if(np==target){ return ans+1; } //if current is in visited set //continue, do not further move it Node nextA(np,ns); string nextAKey = to_string(np)+"_"+to_string(ns); //if the position is positive, moving to the target is meaningful //the second condition is not sure, we refer huahua's code (1.5 is also ok) if(np > 0 && ns< 1.5*target){ //do nothing q.push({np,ns}); //printf("(%d,%d)\n",nextA.m_pos,nextA.m_speed); } //if R move //pos does not change, do not need to check target np = node.first; if(node.second>0){ ns = -1; }else{ ns = 1; } string nextRKey = to_string(np)+"_"+to_string(ns); if(visited.find(nextRKey)==visited.end()){ //only put the node into the queue if it is not visited q.push({np,ns}); visited.insert(nextRKey); //printf("(%d,%d)\n",nextR.m_pos,nextR.m_speed); } }//while current qsize ans++; }//while q empty //does not find the target return ans; } };
542. 01 Matrix
The naive thoughts that call the bfs that use each cell at the start position is easy to exceeds the time. Here we use the multisource bfs. The idea is simple, we just insert all source into the queue, and then start the normal bfs operation. Just assumping there are multiple trees, and if we want to do the bfs at the same time, we just need to put them into the queue. For each layer, the node we processed can be on the different tree, but they are in the same level. We need another metrix to record the distance and we just add 1 if we visit a new node.
classSolution { public: int m_row; int m_col; int X[4] = {1,0,-1,0}; int Y[4] = {0,1,0,-1}; boolvalid(int x, int y){ return x>=0 && y>=0 && x<m_row && y<m_col; } vector<vector<int>> updateMatrix(vector<vector<int>>& mat) { //range the matrix //for each position m_row=mat.size(); m_col=mat[0].size(); vector<vector<int>> ans(m_row, vector<int>(m_col,-1)); queue<pair<int,int>>q; for(int i=0;i<m_row;i++){ for(int j=0;j<m_col;j++){ //put the case with 0 value into the queue if(mat[i][j]==0){ q.push(make_pair(i,j)); ans[i][j]=0; } } } //start the bfs while(!q.empty()){ auto p = q.front(); q.pop(); int cr = p.first; int cc = p.second; //do not need to consider layer explicitly for(int i=0;i<4;i++){ int nr = cr+X[i]; int nc = cc+Y[i]; if(valid(nr,nc) && ans[nr][nc]==-1){ //start to propagate from the source ans[nr][nc]=ans[cr][cc]+1; q.push({nr,nc}); } } } return ans; } };
BFS+DFS
126. Word Ladder II
Compared with the 127, this question requires us to print out the shortest path in explicit way. For bfs, we only remember the distance and the link between two edges, but it does not keep the whole path. We need to use the dfs to trace the whole path. For each time of checking the adjacent nodes, we put them into a map that store the relationship. The key of the map is the current node, the value of the map is a set to store the parent node of the current one.
classSolution { public: vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList){ vector<vector<string>> pathAns; // check if the endword is in the list bool endExist = false; for (auto v : wordList) { if (v == endWord) { endExist = true; break; } }
if (endExist == false) { // end not exist return pathAns; }
// build the dic with the pattern unordered_map<string, set<string>> patternMap; string pattern; wordList.push_back(beginWord); for (auto word : wordList) { for (int i = 0; i < word.length(); i++) { pattern = word; pattern[i] = '*'; patternMap[pattern].insert(word); // printf("build graph pattern %s word // %s\n",pattern.c_str(),word.c_str()); } } // check graph set<string> visited; // bfs // key is the current nodes // value is the parrent node unordered_map <string, set<string>> pathRecord; int res = 1; queue<string> q; q.push(beginWord); int bestRes = INT_MAX;
while (q.empty() == false) { // visit current layer // for the new layer // if jump to the wordEnd direactly the res is 1 int qsize = q.size(); while (qsize > 0) { // get current string currw = q.front(); q.pop(); qsize--; if(visited.find(currw)!=visited.end()){ //this node is visited previously continue; } visited.insert(currw);
//printf("currw %s remain num %d\n", currw.c_str(), qsize); if (currw == endWord) { // the first finded one is the shortest one // we do not need to iterate all possibilities // update the path once find it bestRes = min(bestRes,res); vector<string> path; path.push_back(endWord); getPathDfs(endWord,beginWord,path,pathAns,pathRecord,1,bestRes); } // check all patterns // get to the end // check words in pattern map for (int i = 0; i < currw.length(); i++) { pattern = currw; pattern[i] = '*'; for (auto pattenw : patternMap[pattern]) { // printf("pattern %s pattenw // %s\n",pattern.c_str(),pattenw.c_str()); //if (pathRecord[pattenw].find(pattenw) == pathRecord[pattenw].end()) { if(visited.find(pattenw) == visited.end()){ q.push(pattenw); if(currw!=pattenw){ //do not insert self //printf("insert %s\n",currw.c_str()); pathRecord[pattenw].insert(currw); } } } } }// after while // finsh processing one layer res++; if(res>bestRes){ break; } } return pathAns; } voidgetPathDfs(string current, string& beginStr, vector<string>& path, vector<vector<string>>& ans, unordered_map <string, set<string>>& pathRecord, int layer, int bestLayer){ if(layer>bestLayer){ return; } if(current == beginStr){ //put the path into the results vector<string> revPath = path; reverse(revPath.begin(),revPath.end());
ans.push_back(revPath); return; } //for current node for (auto v:pathRecord[current]){ //next dfs path.push_back(v); getPathDfs(v,beginStr,path,ans,pathRecord, layer+1, bestLayer); //set back path.pop_back(); } return; } };
BFS + sorting
It is usually the hard question when the BFS is used as a subroutine for the other aproaches. Such as 675, I refer to huahua’s code. The question requires to trim the tree from smallest to tallest is actually a label for sorting. Then we can use bfs as a subroutine to compute the dist for each adjacent two points in sorted array. The visited flag and the levelSize techniques are used here. The sorting operation here is a little bit special one, we use the tree hight as the first element of a tuple, subsequent elements are coordinates, then we use first element as the index to do the sorting.
classSolution { public: intcutOffTree(vector<vector<int>>& forest){ //insert into tuple vector vector<tuple<longlongint, int, int>>nodeList; //sort tuple vector int r = forest.size(); if (r==0) return0; int c = forest[0].size();
for(int i=0;i<r;i++){ for(int j=0;j<c;j++){ //only push the one that need to cut //do not contain the element with 0 and 1 //the element with 1 do not need to be cut if(forest[i][j]>1){ nodeList.push_back(make_tuple(forest[i][j],i,j)); } } }
sort(nodeList.begin(),nodeList.end()); int stepCount=0; bool startStep=false; int si=0,sj=0; //bfs comoute dist for each two adjacent node for(int i=0;i<nodeList.size();i++){ int ei = get<1>(nodeList[i]); int ej = get<2>(nodeList[i]); int d = dist(si,sj,ei,ej,forest); if(d==-1){ //no connected path return-1; } stepCount=stepCount+d; //cut the tree at the dest forest[ei][ej]=1; si=ei; sj=ej; } return stepCount; }
intdist(int si, int sj, int ei, int ej, vector<vector<int>>& forest){ //range of forsest if(si==ei && sj==ej) return0; int r = forest.size(); int c = forest[0].size(); vector<vector<int>> move={{-1,0},{0,-1},{1,0},{0,1}}; vector<vector<int>> visited(r, vector<int>(c,0)); //dist from start to end queue<pair<int, int>> q; //init queue q.push({si,sj}); visited[si][sj]=1; int dist=0; //bfs while(q.empty()==false){ int levelSize = q.size(); while (levelSize>0){ //extract node from queue and process node auto node = q.front(); q.pop(); for(int i=0;i<4;i++){ int nexti=node.first+move[i][0]; int nextj=node.second+move[i][1]; if(nexti>=0 && nexti <r && nextj>=0 && nextj<c){ if(forest[nexti][nextj]>=1){ if(nexti==ei && nextj==ej){ return dist+1; }else{ if(visited[nexti][nextj]==0){ q.push({nexti,nextj}); visited[nexti][nextj]=1; } } } } } levelSize=levelSize-1; } dist=dist+1; } //not find the path to dest return-1; } };
Multi sources BFS
934 is a little bit complicated in structures, it can be viewed as DFS+Multisources BFS question. The shortest path between two island can be viewed as the sortest path from the set 1 to the set 2. Since the question said there are exactly two islands, so we only need to identify one cluster. The process to identify one cluster is to use the DFS (which is simple in code implementation). We just need to go through each element of the grid, when we find the one that equals to 1, it can be viewed as the start point of one island, then we can use the dfs to iterate the graph and find all elements in this island. After detecting it, we can use the bfs to identify the shortest path from current set to the position that have 1 (the shortest path to another island).
The code is listed as follows, it uses lambda expression to find the first element equals to 1, then using dfs to find all elements of first island (using vector + visited flag is more efficient than using the set). At last, we use the multisource BFS to compute the distance. This is a good video to discuss these type of questions
classSolution { vector<vector<int>> dir{{-1,0},{1,0},{0,-1},{0,1}}; int m_r; int m_c; public: voidfindisolated(int r, int c, vector<vector<int>>& grid, vector<pair<int, int>>& island, vector<vector<int>>& visited){ //insert current elements island.push_back({r,c}); visited[r][c]=1; //find the adjacent node in island in recursion way //only call recursion when next level is valid for(int i=0;i<4;i++){ int nr=r+dir[i][0]; int nc=c+dir[i][1]; if(nr<0 || nr>=this->m_r || nc<0 || nc>=this->m_c){//outof bounuds continue; } //do not further check if the current node have been checked //or using find operation for set island.find{nr,nc}!=island.end() if(visited[nr][nc]==1 || grid[nr][nc]==0){ //current node is visited or not belongs to the island continue; } //when subchild is valid one then recursion findisolated(nr,nc,grid,island,visited); } return; } intshortestBridge(vector<vector<int>>& grid){ this->m_r = grid.size(); this->m_c = grid[0].size(); int ir,ic;//start position of first island //step1, find the first island //using lambda expression to find the first element that is not 0 [&](){ for(int i=0;i<this->m_r;i++){ for(int j=0;j<this->m_c;j++){ if(grid[i][j]==1){ ir=i; ic=j; return; } } } }(); vector<pair<int, int>> island; vector<vector<int>> visited(this->m_r, (vector<int>(this->m_c,0))); findisolated(ir,ic,grid,island,visited); //step2, multisource bfs to measure dist between two islands int step = 0; queue<pair<int, int>>q; //new visited flag for bfd vector<vector<int>> visitedbfs(this->m_r, (vector<int>(this->m_c,0))); //put all set number into the set for(auto v:island){ q.push(v); visitedbfs[v.first][v.second]=1; } while(!q.empty()){ int qsize = q.size(); while(qsize>0){ //getting elements and poping out one node auto p = q.front(); q.pop(); qsize--; //all adjacents nodes for(int i=0;i<4;i++){ int nr = p.first+dir[i][0]; int nc = p.second+dir[i][1]; //out of bounuds if(nr<0 || nr>=this->m_r || nc<0 || nc>=this->m_c){ continue; } //if curent is visited, we can use the set operation //if(visited.find({nr,nc})!=visited.end()){ if(visitedbfs[nr][nc]==1){ continue; } //find out the destination (another island) if(grid[nr][nc]==1){ return step; } //if current is not 1, it is 0, put into the queue q.push({nr,nc}); visitedbfs[nr][nc]=1; } }//while after processing nodes in current layer step++; } return step; } };
