算法
(DFS) O(n23k)
在深度优先搜索中，最重要的就是考虑好搜索顺序。
我们先枚举单词的起点，然后依次枚举单词的每个字母。
过程中需要将已经使用过的字母改成一个特殊字母，以避免重复使用字符。
时间复杂度分析：单词起点一共有 n2 个，单词的每个字母一共有上下左右四个方向可以选择，但由于不能走回头路，所以除了单词首字母外，仅有三种选择。所以总时间复杂度是 O(n23k)。
C++ 代码
class Solution {
public:
bool hasPath(vector<vector<char>>& matrix, string str) {
for (int i = 0; i < matrix.size(); i ++ )
for (int j = 0; j < matrix[i].size(); j ++ )
if (dfs(matrix, str, 0, i, j))
return true;
return false;
}
bool dfs(vector<vector<char>> &matrix, string &str, int u, int x, int y) {
if (matrix[x][y] != str[u]) return false;
if (u == str.size() - 1) return true;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
char t = matrix[x][y];
matrix[x][y] = '*';
for (int i = 0; i < 4; i ++ ) {
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < matrix.size() && b >= 0 && b < matrix[a].size()) {
if (dfs(matrix, str, u + 1, a, b)) return true;
}
}
matrix[x][y] = t;
return false;
}
};
## 想不到
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};这一句是啥意思呀
代表上下左右移动，dx的-1代表向左移动，1代表向右移动。dy的-1代表向上移动，1代表向下移动
class Solution { public: bool visited[901][901]; int pos[4][2] = { { -1 , 0 } , { 0 , 1 } , { 1 , 0 } , { 0 , -1 } }; bool hasPath(vector<vector<char>>& matrix, string &str) { if(matrix.empty()) return false; memset(visited , 0 , sizeof(visited)); for(int i = 0 ;i < matrix.size() ; i ++) for(int j = 0 ;j < matrix[i].size() ; j ++) if(matrix[i][j] == str[0]) { visited[i][j] = 1; if(find_path(matrix , str , 1 , i , j)) return true; visited[i][j] = 0; } return false; } bool find_path(vector<vector<char>>& matrix , string& str ,int now , int x , int y) { if(now == str.size()) return true; for(int i = 0 ;i < 4 ; i ++) { int newx = x + pos[i][0] , newy = y + pos[i][1]; if(is_feasible(newx , newy , matrix) && matrix[newx][newy] == str[now]){ visited[newx][newy] = 1; if(find_path(matrix , str , now + 1 , newx , newy)) return true; visited[newx][newy] = 0; } } return false; } // bool find_path(vector<vector<char>>& matrix , string& str, int now ,int x, int y) { // if(now == str.size() - 1) return true; // bool flag = false; // for(int i =0 ;i < 4 ; i ++) { // int newx = x + pos[i][0] , newy = y + pos[i][1]; // if(is_feasible(newx , newy , matrix) && matrix[newx][newy] == str[now + 1]) { // visited[newx][newy] = 1; // flag = find_path(matrix , str , now + 1 , newx , newy); // visited[newx][newy] = 0; // if(flag) return true; // } // } // return false; // } bool is_feasible(int x, int y , vector<vector<char>>& matrix) { return x >= 0 && x < matrix.size() && y >= 0 && y < matrix[0].size() && !visited[x][y]; } };没想到用特殊字符替代的这种方法，学到了，习惯性开visited数组浪费了好多空间。
class Solution { public: int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; bool st[1000][1000]; int n, m; bool dfs(int x, int y, int u, string& str, vector<vector<char>>& matrix) { // 错误写法 if (u == str.size()) return true; if (matrix[x][y] != str[u]) return false; // 正确写法 // if (matrix[x][y] != str[u]) return false; // if (u == str.size() - 1) return true; st[x][y] = true; for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (nx < 0 || nx >= n || ny < 0 || ny >= m || st[nx][ny]) continue; if (dfs(nx, ny, u + 1, str, matrix)) return true; } st[x][y] = false; return false; } bool hasPath(vector<vector<char>>& matrix, string &str) { if (matrix.size() == 0 || matrix[0].size() == 0) return false; n = matrix.size(), m = matrix[0].size(); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (dfs(i, j, 0, str, matrix)) return true; } } return false; } };请问换成错误代码那两行之后错在哪了？ 过了15个样例
你好，我的理解是这个例子
str=amartix=[a]第一步成功了，但是在继续dfs的时候是不能继续dfs的，因为
if (nx < 0 || nx >= n || ny < 0 || ny >= m || st[nx][ny]) continue;下标全都越界，进入continue,没法进入预计的dfs（1）请问大佬们，这个哪里出错了 只不过是用x=x+dx[i],y=y+dy[i];就出错了，是产生歧义了吗，还是这个会改变x的值，求大佬解答Orz
class Solution {
public:
vector[HTML_REMOVED]path;
bool hasPath(vector[HTML_REMOVED]>& matrix, string &str) {
for( int i=0;i[HTML_REMOVED]>& matrix, string &str,int x,int y,int u)
{
if(matrix[x][y]!=str[u]) return false;
if(u==str.size()-1) return true;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
char ch=matrix[x][y];
matrix[x][y]=’*’;
for(int i=0;i<4;i++)
{
x=x+dx[i];y=y+dy[i];
if(x>=0&&x[HTML_REMOVED]=0&&y<matrix[x].size())
{
if(dfs(matrix,str,x,y,u+1)) return true;
}
}
matrix[x][y]=ch;
return false;
}
};
改变x、y的值了，恢复现场的时候会改变matrix其他位置的值
大佬们，请问这个是哪里出错呢
class Solution {
public:
int curi,curj;
int dpi[4]={0,0,1,-1};
int dpj[4]={1,-1,0,0};
int a[907][907];
bool hasPath(vector[HTML_REMOVED]>& matrix, string &str) {
memset(a,0,sizeof(a));
int n=matrix.size();
if(n==0)
return false;
int m=matrix[0].size();
int i,j;
int p=0;
for(i=0;i[HTML_REMOVED]> &m,string &s,int sum)
{
if(sum==s.size())
return true;
if(curi<0||curj<0||curi>=m.size()||curj>=m[0].size()||(m[curi][curj]!=s[sum]&&sum[HTML_REMOVED]=0&&curj>=0&&curi<m.size()&&curj<m[0].size()&&m[curi][curj]==s[sum]&&sum<s.size())
return dfs(curi+dpi[0],curj+dpj[0],m,s,sum)||dfs(curi+dpi[1],curj+dpj[1],m,s,sum)||dfs(curi+dpi[2],curj+dpj[2],m,s,sum)||dfs(curi+dpi[3],curj+dpj[3],m,s,sum);
}
};
想知道n²3^k那个k是怎么打上去的TAT
O(n23k)
$(n^23^k)$哇 谢谢!
matrix[x][y] = t;这一步感觉没啥用吧
恢复现场吧，这是传的引用，matrix的值被修改了，如果不恢复的话不然下一次dfs的时候就会有问题
恢复现场，保证在搜索一条路径时一个字母只用一次
这个题的思路和蛇形矩阵好像啊
这个为什么会段错误呢qaq
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; bool dfs(vector<vector<char>>v,vector<vector<bool>>&exist,string s,string str,int x,int y){ s+=v[x][y]; if(s==str) return true; if(s.length()>str.length()) return false; if(x<0||x>=v.size()||y<0||y>=v[0].size())// 循环里再判断出界 return false; exist[x][y]=true; for(int i=0;i<4;i++){ int dx=x+dir[i][0],dy=y+dir[i][1]; if(dx>=0&&dx<v.size()&&dy>=0&&dy<v[0].size()&&!exist[dx][dy]) if(dfs(v,exist,s,str,dx,dy)) return true; } exist[x][y]=false; return false; } //没有指定一定从原点开始 bool hasPath(vector<vector<char>>& matrix, string &str) { if(matrix[0].size()==0||matrix.size()==0) return false; int m=matrix.size(),n=matrix[0].size(); vector<vector<bool>>exist(m,vector<bool>(n,false)); for(int i = 0; i < matrix.size(); i++) { for (int j = 0; j < matrix[0].size(); j++) { if (matrix[i][j] == str[0]) { bool a=dfs(matrix,exist,"",str,i,j); if (a){ return true; } } } } return false; }错误数据是二维数组为空
if(matrix[0].size()==0||matrix.size()==0) return false;这句会先执行
matrix[0].size()==0,对空数组取下标为0的元素就越界了。可以改为if(matrix.size()==0||matrix[0].size()==0) return false;第一个条件为true就不会执行第二个语句了
666
if (matrix[x][y] != str[u]) return false; if (u == str.size() - 1) return true;请问有大佬能解释一下这两行是什么意思吗?
第一个if是指当前字符串不匹配直接返回false
第二个if是指当第当前字符匹配且当前为最后一个字符时，直接返回true
明白了~谢谢！
谢谢！
而且这两行顺序还不能换
避免最后一个u不同的情况
感谢
大佬，为什么这两行的顺序不能换呢？
我 y 总写的代码好骚啊！
y总，用来保存matrix[x][y]值的临时变量t是不是可以不用定义？因为程序进行到了这里，matrix[x][y]==str[u]是成立的，还原matrix[x][y]的时候直接用str[u]是不是就可以啦
可以的。
定义的变量好多，看混淆了都
这题变量不多呀hh
您好，请问您一下为什么这个方法在LeetCode上运行，会显示 当输入是[[“a”]]”ab” 时，会输出true
已找到问题所在，谢谢啦~
好滴
为什么这一种写法是 cur.size() == index, 而上面这种是cur.size() - 1 == index
bool backtrack(vector<vector<char>> &board, int row, int col, const string &word, int idx) { if(word.size() == idx) return true; if(row < 0 || row >= board.size() || col < 0 || col >= board[0].size()) return false; if(word[idx] != board[row][col]) return false; board[row][col] = '*'; if (backtrack(board, row - 1, col, word, idx + 1) || backtrack(board, row + 1, col, word, idx + 1) || backtrack(board, row, col - 1, word, idx + 1) || backtrack(board, row, col + 1, word, idx + 1)) return true; board[row][col] = word[idx]; return false; } public: bool exist(vector<vector<char>>& board, string word) { if (board.empty() || board[0].empty()) return word.empty(); for (int row = 0; row < board.size(); ++row) { for (int col = 0; col < board[0].size(); ++col) { if (backtrack(board, row, col, word, 0)) return true; } } return false; }都是可以的。
y总，貌似这两句交换顺序，就通过不了了
if(matrix[x][y]!=str[u]) return false; if(u==str.size()-1) return true;最后一个位置没有判断是否相同就直接返回true，肯定不对啊。
而且第一行u一定不会越界
if (matrix[x][y] != str[n]) return false; if (n == str.size() - 1) return true;yls，为什么上面的可以过，下面的就错了呢？
if (n == str.size()) return true; if (matrix[x][y] != str[n]) return false;if (n == str.size())和if (n == str.size() - 1)不等价。另外调试代码要学会用printf大法，这样学起来会快一些。请问OJ上也能用printf吗？
能用，没问题。
但是在下面那种方式中，运行到if (n == str.size())时，所有的字符都已匹配完，所以应该也没问题才对啊，这里不太明白。。
是不是因为这样：
虽然n个字符已经匹配完成，但没有return退出当前函数的话，会继续执行下面的代码，那么在当前函数里，会以n为起点继续去搜索，所以出了问题。
当输入是
[["a"]], "a"时下面的写法会返回false。下面的写法，如果输入是单字符，就进不去for循环然后直接返回false
能进去for循环，但是进不去for循环里边的第一个if判断，因为单个字符无论向哪个方向移动，都会超出边界，所以四个方向搜索完以后，最后输出false
嗯
对滴。
虽然能理解，但还是让人心情失落，又不能说玄学
如果测试数据为[[“A”]] “A”,按照上述程序会输出false啊，因为进不去for循环中的if语句
for (int i = 0; i < 4; i ++ ) { int a = x + dx[i], b = y + dy[i]; if (a >= 0 && a < matrix.size() && b >= 0 && b < matrix[a].size()) { if (dfs(matrix, str, u + 1, a, b)) return true; } }我运行了一遍，会输出
true。它应该是在if(u == str.length() - 1) return true;时就返回了true的