22
这道题的大体思路还是回溯，可以把n对括号想象成一个长度是2*n的数组，这样就能用回溯的角度看问题。因为有左右括号的限制，所以这里先放左括号，当左括号数量等于n的时候再开始放右括号，分别用两个变量保存左右括号的数量，回溯时右括号一定要小于左括号的数量。
79
这道题虽然是中等题但是感觉挺难的。这道题的思路是二维数组内的每一个节点都可能是word的起点，所以需要以二维数组内的节点作为起始，编写一个check函数来验证这个点行不行。check函数里面是回溯的思路，对word里面的每一个值做验证，如果当前值满足条件才对word下一个值验证，否则就直接函数返回，这里的下一步验证就是具体回溯的代码，需要验证在二维数组中该节点的上下左右的情况。具体代码如下
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
for(int i=0;i<board.size();i++)
{
for(int j=0;j<board[0].size();j++)
{
vector<vector<bool>> visited(board.size(),vector<bool>(board[0].size(),false));
if(dfs(board,word,visited,0,i,j)) return true;
}
}
return false;
}
bool dfs(vector<vector<char>> &board,string &word,vector<vector<bool>> &visited,int w_index,int i,int j)
{
if(w_index==word.size())
{
return true;
}
if(i>=board.size() || i<0 || j> board[0].size() ||j<0|| visited[i][j]==true || word[w_index]!=board[i][j])
return false;
visited[i][j]=true;
if(dfs(board,word,visited,w_index+1,i+1,j) ||
dfs(board,word,visited,w_index+1,i-1,j) ||
dfs(board,word,visited,w_index+1,i,j+1) ||
dfs(board,word,visited,w_index+1,i,j-1))
return true;
visited[i][j]=false;
return false;
}
};
131
这道题整体的思路是回溯，与以往不同的是在回溯之前需要判断这个字符串是不是回文的，单独写一个check函数放在回溯之前就行。
