|
請(qǐng)?jiān)O(shè)計(jì)一個(gè)函數(shù)，用來判斷在一個(gè)矩陣中是否存在一條包含某字符串所有字符的路徑。路徑可以從矩陣中的任意一個(gè)格子開始，每一步可以在矩陣中向左，向右，向上，向下移動(dòng)一個(gè)格子。如果一條路徑經(jīng)過了矩陣中的某一個(gè)格子，則該路徑不能再進(jìn)入該格子。 例如下面的矩陣包含了一條 bfce 路徑。（因?yàn)轭}目中的矩陣是用一維數(shù)組來表示二維數(shù)組的） 來源：?？途W(wǎng) 分析：回溯算法
這是一個(gè)可以用回朔法解決的典型題。首先，在矩陣中任選一個(gè)格子作為路徑的起點(diǎn)。如果路徑上的第i個(gè)字符不是ch，那么這個(gè)格子不可能處在路徑上的
第i個(gè)位置。如果路徑上的第i個(gè)字符正好是ch，那么往相鄰的格子尋找路徑上的第i 1個(gè)字符。除在矩陣邊界上的格子之外，其他格子都有4個(gè)相鄰的格子。
重復(fù)這個(gè)過程直到路徑上的所有字符都在矩陣中找到相應(yīng)的位置。
由于回朔法的遞歸特性，路徑可以被開成一個(gè)棧。當(dāng)在矩陣中定位了路徑中前n個(gè)字符的位置之后，在與第n個(gè)字符對(duì)應(yīng)的格子的周圍都沒有找到第n 1個(gè)
字符，這個(gè)時(shí)候只要在路徑上回到第n-1個(gè)字符，重新定位第n個(gè)字符。
由于路徑不能重復(fù)進(jìn)入矩陣的格子，還需要定義和字符矩陣大小一樣的布爾值矩陣，用來標(biāo)識(shí)路徑是否已經(jīng)進(jìn)入每個(gè)格子。 當(dāng)矩陣中坐標(biāo)為（row,col）的
格子和路徑字符串中相應(yīng)的字符一樣時(shí)，從4個(gè)相鄰的格子(row,col-1),(row-1,col),(row,col 1)以及(row 1,col)中去定位路徑字符串中下一個(gè)字符
如果4個(gè)相鄰的格子都沒有匹配字符串中下一個(gè)的字符，表明當(dāng)前路徑字符串中字符在矩陣中的定位不正確，我們需要回到前一個(gè)，然后重新定位。
一直重復(fù)這個(gè)過程，直到路徑字符串上所有字符都在矩陣中找到合適的位置
鏈接：https://www./questionTerminal/c61c6999eecb4b8f88a98f66b273a3cc 來源：?？途W(wǎng) 核心思路：回溯法 1.先將matrix字符串映射為字符矩陣； 2.從原字符串中找到第一個(gè)跟str[0]相等的字符，得到其對(duì)應(yīng)的在矩陣中的位置[r,c] 1）從[r,c]開始按 上、左、右、下的順序搜索； 2）每當(dāng)搜索到一個(gè)節(jié)點(diǎn)，先判斷path是否包括它，包括就說明已經(jīng)經(jīng)過此節(jié)點(diǎn)，不能 再經(jīng)過了；如果不包括，就將其加入path容器 3）直到搜索到str[length - 1]節(jié)點(diǎn)，說明成功找到，標(biāo)記result為true，標(biāo)記 isFinished為true,盡快結(jié)束所有的遞歸操作 4）如果某節(jié)點(diǎn)起的 上、左、右、下 都搜索過但還沒找到結(jié)果，說明經(jīng)過此節(jié)點(diǎn)的路 徑都不滿足題意，將其從path中刪除，回溯到上一層繼續(xù)找。 （PS:確實(shí)是回溯法，不過代碼有點(diǎn)長(zhǎng)，實(shí)現(xiàn)的有點(diǎn)繁雜）
public class Solution {
private final static int[][] dir = {{0,-1},{0,1},{-1,0},{1,0}};
private int row, col;
public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
{
if(row==0 || col==0) return false;
this.row = row;
this.col = col;
boolean[][] flag = new boolean[row][col];
//char[][] a = build(matrix);
char a[][] = new char[row][col];
for(int i=0,k=0; i<row; i ) {
for(int j=0; j<col; j ) {
a[i][j] = matrix[k ];
}
}
for(int i=0; i<row; i ) {
for(int j=0; j<col; j )
if(dfs(a,str,flag,0,i,j))
return true;
}
return false;
}
private boolean dfs(char[][] a,char[] str,boolean[] flag,int pathLen, int r,int c){
if(pathLen == str.length) return true;
if(r<0 || r>=row || c<0 || c>=col || a[r][c] != str[pathLen] || flag[r][c])
return false;
flag[r][c] = true;
for(int[] d:dir) {
if(dfs(a,str,flag,pathLen 1,r d[0],c d[1]))
return true;
}
flag[r][c]=false;
return false;
}
鏈接：https://www./questionTerminal/c61c6999eecb4b8f88a98f66b273a3cc
來源：牛客網(wǎng)
public boolean hasPath(char[] matrix, int rows, int cols, char[] str){
boolean[] visited = new boolean[matrix.length];
for (int i = 0; i < rows; i ) {
for (int j = 0; j < cols; j ) {
if (searchFromHere(matrix,rows,cols,i,j,0,str,visited))
return true;
}
}
// System.out.println(Arrays.toString(visited));
return false;
}
public boolean searchFromHere(char[] matrix,int rows,int cols,int r,int c,int index,char[] str,boolean[] visited){
if (r < 0 || r >= rows || c < 0 || c >= cols || matrix[r * cols c] != str[index] || visited[r * cols c])
return false;
if (index == str.length - 1) return true;
visited[r * cols c] = true;
if (searchFromHere(matrix,rows,cols,r - 1,c,index 1,str,visited) ||
searchFromHere(matrix,rows,cols,r,c -1,index 1,str,visited) ||
searchFromHere(matrix,rows,cols,r 1,c,index 1,str,visited) ||
searchFromHere(matrix,rows,cols,r,c 1,index 1,str,visited))
return true;
visited[r * cols c] = false;
return false;
}
鏈接：https://www./questionTerminal/c61c6999eecb4b8f88a98f66b273a3cc 鏈接：https://www./questionTerminal/c61c6999eecb4b8f88a98f66b273a3cc
來源：牛客網(wǎng)
public class Solution {
public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
{
//標(biāo)志位，初始化為false
boolean[] flag = new boolean[matrix.length];
for(int i=0;i<rows;i ){
for(int j=0;j<cols;j ){
//循環(huán)遍歷二維數(shù)組，找到起點(diǎn)等于str第一個(gè)元素的值，再遞歸判斷四周是否有符合條件的----回溯法
if(judge(matrix,i,j,rows,cols,flag,str,0)){
return true;
}
}
}
return false;
}
//judge(初始矩陣，索引行坐標(biāo)i，索引縱坐標(biāo)j，矩陣行數(shù)，矩陣列數(shù)，待判斷的字符串，字符串索引初始為0即先判斷字符串的第一位)
private boolean judge(char[] matrix,int i,int j,int rows,int cols,boolean[] flag,char[] str,int k){
//先根據(jù)i和j計(jì)算匹配的第一個(gè)元素轉(zhuǎn)為一維數(shù)組的位置
int index = i*cols j;
//遞歸終止條件
if(i<0 || j<0 || i>=rows || j>=cols || matrix[index] != str[k] || flag[index] == true)
return false;
//若k已經(jīng)到達(dá)str末尾了，說明之前的都已經(jīng)匹配成功了，直接返回true即可
if(k == str.length-1)
return true;
//要走的第一個(gè)位置置為true，表示已經(jīng)走過了
flag[index] = true;
//回溯，遞歸尋找，每次找到了就給k加一，找不到，還原
if(judge(matrix,i-1,j,rows,cols,flag,str,k 1) ||
judge(matrix,i 1,j,rows,cols,flag,str,k 1) ||
judge(matrix,i,j-1,rows,cols,flag,str,k 1) ||
judge(matrix,i,j 1,rows,cols,flag,str,k 1) )
{
return true;
}
//走到這，說明這一條路不通，還原，再試其他的路徑
flag[index] = false;
return false;
}
|
|
|
