在矩阵中寻找字符串
For example,
Given board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.
题目描述：
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
思路分析：
回溯法解决，从矩阵中一个点开始，如果该点的值等于字符串中第一个值，那么接下来我们可以从该点的左上右下节点继续搜索。但是不能重复遍历，如果最终能找到一条字符串中的路径那么返回true，如果不能返回false。
代码：
public boolean exist(char[][]board,String word){
if(board==null||board.length==0)
return false;
if(word==null||word.length()==0)
return true;
int m=board.length;
int n=board[0].length;
boolean[][]flag=new boolean[m][n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(backtracking(0,i,j,board,word,flag))
return true;
}
}
return false;
}
public boolean backtracking(int k,int i,int j,char[][]board,String word,boolean[][]flag){
if(k==word.length())
return true;
if(i<0||i>=board.length||j<0||j>=board[0].length||flag[i][j]==true||word.charAt(k)!=board[i][j])
return false;
flag[i][j]=true;
if(backtracking(k+1,i+1,j,board,word,flag)||backtracking(k+1,i-1,j,board,word,flag)||backtracking(k+1,i,j+1,board,word,flag)||backtracking(k+1,i,j-1,board,word,flag))
return true;
flag[i][j]=false;
return false;
}