【Hot100】LeetCode—79. 单词搜索

---

• 原题链接：79. 单词搜索

---

1- 思路

回溯

思路：① 遍历每个单元格（作为起点）、②对每个单元格进行回溯（起点回溯）
1- 起点

• 用两层 for 循环遍历每个单元格，之后对当前单元格进行 dfs

2- 回溯操作

• 由于需要对每个单元格进行回溯，所以 i 和 j的位置，回溯函数必须要知道，因此传参中必须有 i 和 j

---

2- 实现

⭐79. 单词搜索——题解思路

class Solution {boolean[][] used ;public boolean exist(char[][] board, String word) {used = new boolean[board.length][board[0].length];int row = board.length;int col = board[0].length;for(int i = 0 ; i < row;i++){for(int j = 0 ; j < col;j++){if(backTracing(board,word,0,i,j)){return true;}}}return false;}int[][] dir = {{-1,0},{0,-1},{1,0},{0,1}};public boolean backTracing(char[][] board,String word,int index,int i ,int j ){// 结果收集if(word.length() == index){return true;}// 结束判断if( i < 0 || i>=board.length || j<0 || j>=board[0].length || used[i][j] || board[i][j] != word.charAt(index)){return false;}// 回溯// 标记为已使用used[i][j] = true;for(int[] d:dir){int nextX = i + d[0];int nextY = j + d[1];if(backTracing(board,word,index+1,nextX,nextY)){return true;}}used[i][j] = false;return false;}
}

---

3- ACM 实现

public class exist {static boolean[][] used ;public static boolean exist(char[][] board, String word) {used = new boolean[board.length][board[0].length];int row = board.length;int col = board[0].length;for(int i = 0 ; i < row;i++){for(int j = 0 ; j < col;j++){if(backTracing(board,word,0,i,j)){return true;}}}return false;}static int[][] dir = {{-1,0},{0,-1},{1,0},{0,1}};public static boolean backTracing(char[][] board,String word,int index,int i ,int j ){// 结果收集if(word.length() == index){return true;}// 结束判断if( i < 0 || i>=board.length || j<0 || j>=board[0].length || used[i][j] || board[i][j] != word.charAt(index)){return false;}// 回溯// 标记为已使用used[i][j] = true;for(int[] d:dir){int nextX = i + d[0];int nextY = j + d[1];if(backTracing(board,word,index+1,nextX,nextY)){return true;}}used[i][j] = false;return false;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String boardInput = scanner.nextLine();String word = scanner.nextLine();char[][] board = parseBoard(boardInput);boolean res = exist(board, word);System.out.println(res);}private static char[][] parseBoard(String input) {input = input.substring(1, input.length() - 1); // Remove outer bracketsString[] rows = input.split("],\\[");int rowCount = rows.length;int colCount = rows[0].split(",").length;char[][] board = new char[rowCount][colCount];for (int i = 0; i < rowCount; i++) {String[] cols = rows[i].replaceAll("[\\[\\]\"]", "").split(",");for (int j = 0; j < colCount; j++) {board[i][j] = cols[j].charAt(0);}}return board;}
}

---