https://www.cnblogs.com/grandyang/p/4332313.html
在一个矩阵中能不能找到string的一条路径
这个题使用的是dfs。但这个题与number of islands有点不同，那个题中visited过的就不用再扫了，但是这个需要进行回溯回来。
所以使用了visited[i][j] = false;
本质区别还是那个题是找一片区域，这个题更像是找一条路径。
错误一：如果board不引用，会报超内存
错误二：
这个写法和正确写法基本相同，但错误写法需要每次都去遍历flag1、flag2、flag3、flag4，正确写法中，如果flag1为真，就不用再去遍历flag2、3、4，这样就节省了许多时间。
所以这个写法报的错误是在有一个比较大的case超时。
https://blog.csdn.net/CV2017/article/details/82659742
或运算符，左右两边通常为关系或相等表达式，第一个操作数将完全运算，仅当第一个操作数的计算结果为 false 时计算第二个操作数，当第一个操作数的计算结果为 true 时,不用计算第二个操作数和这之后的操作数，直接运行后面的代码了
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
int m = board.size();
int n = board[].size();
vector<vector<bool> > visited(m,vector<bool>(n));
for(int i = ;i < m;i++){
for(int j = ;j < n;j++){
int index = ;
if(exit(board,word,i,j,index,visited))
return true;
}
}
return false;
}
bool exit(vector<vector<char>>& board,string word,int i,int j,int index,vector<vector<bool>>& visited){
if(index == word.size())
return true;
if(i < || i >= board.size() || j < || j >= board[].size() || visited[i][j] == true || board[i][j] != word[index])
return false;
visited[i][j] = true;
bool flag1 = exit(board,word,i - ,j,index+,visited);
bool flag2 = exit(board,word,i + ,j,index+,visited);
bool flag3 = exit(board,word,i,j - ,index+,visited);
bool flag4 = exit(board,word,i,j + ,index+,visited);
visited[i][j] = false;
return flag1 || flag2 || flag3 || flag4;
}
};
正确写法：
如果第一个字符不相同，就继续遍历，这个操作可以减少搜索的个数
vector<vector<bool>> visited(m,vector<bool>(n,false));不要写在for循环里面，其实每次递归都是将置为true的又置为了false的。
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
int m = board.size();
int n = board[].size();
vector<vector<bool> > visited(m,vector<bool>(n,false));
for(int i = ;i < m;i++){
for(int j = ;j < n;j++){
if(board[i][j] != word[])
continue;
int index = ;
if(exit(board,word,i,j,index,visited))
return true;
}
}
return false;
}
bool exit(vector<vector<char>>& board,string word,int i,int j,int index,vector<vector<bool>>& visited){
if(index == word.size())
return true;
if(i < || i >= board.size() || j < || j >= board[].size() || visited[i][j] == true || board[i][j] != word[index])
return false;
visited[i][j] = true;
bool res = exit(board,word,i - ,j,index+,visited) || exit(board,word,i + ,j,index+,visited) || exit(board,word,i,j - ,index+,visited) || exit(board,word,i,j + ,index+,visited);
visited[i][j] = false;
return res;
}
};
212. Word Search II
https://www.cnblogs.com/grandyang/p/4516013.html
这个题是trie树与dfs相结合的题目，将所有需要搜索的词存入trie树当中，然后在二维数组中dfs搜索。
这个题的trie树的定义和leetcode 208. Implement Trie (Prefix Tree) 、211. Add and Search Word - Data structure design的不太一样，208、211定义了一个isWord
用来表示是否是词的结尾。这个题定义的则是一个string，并且这个string存储的就是整个单词，这样既可以用来表示结尾，又可以获得搜索的整个词。这样做主要是由于
这个题目本身要求返回搜索成功的词。
这个题在搜索到词后，还需要clear掉str，因为题目要求同一个词只返回一个，例子如下：
Input:
[["a","a"]]
["a"]
Output:
["a","a"]
Expected:
["a"]
class Solution {
public:
struct TrieNode{
TrieNode* child[];
string str;
TrieNode():str(""){
for(int i = ;i < ;i++)
child[i] = NULL;
}
};
struct Trie{
TrieNode* root;
Trie():root(new TrieNode()){
}
void insert(string s){
TrieNode* p = root;
for(char tmp : s){
int i = tmp - 'a';
if(!p->child[i])
p->child[i] = new TrieNode();
p = p->child[i];
}
p->str = s;
return;
}
};
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
vector<string> res;
if(board.empty() || board[].empty() || words.empty())
return res;
int m = board.size(),n = board[].size();
Trie T;
for(string word : words)
T.insert(word);
vector<vector<bool>> visited(m,vector<bool>(n,false));
for(int i = ;i < m;i++){
for(int j = ;j < n;j++){
if(T.root->child[board[i][j] - 'a'])
findWords(board,T.root->child[board[i][j] - 'a'],visited,i,j,res);
}
}
return res;
}
void findWords(vector<vector<char>>& board,TrieNode* p,vector<vector<bool>>& visited,int i,int j,vector<string>& res){
if(!p->str.empty()){
res.push_back(p->str);
p->str.clear();
}
visited[i][j] = true;
for(auto dir : dirs){
int x = i + dir[];
int y = j + dir[];
if(x < || x >= board.size() || y < || y >= board[].size() || visited[x][y] == true || p->child[board[x][y] - 'a'] == NULL)
continue;
findWords(board, p->child[board[x][y] - 'a'],visited, x, y, res);
}
visited[i][j] = false;
return;
}
private:
vector<vector<int>> dirs{{-,},{,},{,-},{,}};
};