判斷數組中是否含有某一字元串
問題描述:
請設計一個函數,用來判斷在一個矩陣中是否存在一條包含某字元串所有字元的路徑。路徑可以從矩陣中的任意一格開始,每一步可以在矩陣中向左、右、上、下移動一格。如果一條路徑經過了矩陣的某一格,那麼該路徑不能再次進入該格子。例如,在下面的3×4的矩陣中包含一條字元串“bfce”的路徑(路徑中的字母用加粗标出)。
[[“a”,“b”,“c”,“e”],
[“s”,“f”,“c”,“s”],
[“a”,“d”,“e”,“e”]]
但矩陣中不包含字元串“abfb”的路徑,因為字元串的第一個字元b占據了矩陣中的第一行第二個格子之後,路徑不能再次進入這個格子。
來源:劍指offer 12
代碼:
public boolean exist(char[][] board, String word) {
char[] words = word.toCharArray();
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[0].length; j++) {
if(dfs(board, words, i, j, 0)) return true;
}
}
return false;
}
boolean dfs(char[][] board, char[] word, int i, int j, int k) {
if(i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) return false;
if(k == word.length - 1) return true;
char tmp = board[i][j];
board[i][j] = '/';
boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) ||
dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);
board[i][j] = tmp;
return res;
}
}