单词搜索题目链接https://leetcode.cn/problems/word-search/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答int[] directionX new int[]{1,-1,0,0}; int[] directionY new int[]{0,0,1,-1}; boolean[] visited; public boolean exist(char[][] board, String word) { int m board.length, n board[0].length; visited new boolean[m*n]; boolean flag false; for(int i0; im; i){ for(int j0; jn; j){ if(board[i][j] word.charAt(0)){ visited[i * n j] true; flag dfs(board, word, i, j, 0); visited[i * n j] false; if(flag){ break; } } } if(flag){ break; } } return flag; } public boolean dfs(char[][] board, String word, int x, int y, int cur){ if(cur word.length()-1){ return true; } int m board.length, n board[0].length; boolean valid false; for(int i0; i4; i){ int xx x directionX[i]; int yy y directionY[i]; if(xx 0 xx m yy 0 yy n visited[xx * n yy] false board[xx][yy] word.charAt(cur1)){ visited[xx * n yy] true; valid dfs(board, word, xx, yy, cur1); visited[xx * n yy] false; if(valid){ break; } } } return valid; }分析代码的时间复杂度为O(m * n * 3^L)其中L为字符串word的长度空间复杂度为O(m*n)。解题思路采用基本的递归回溯方法解题思路较简单故不赘述。看了官方题解后的解答public boolean exist(char[][] board, String word) { int h board.length, w board[0].length; boolean[][] visited new boolean[h][w]; for (int i 0; i h; i) { for (int j 0; j w; j) { boolean flag check(board, visited, i, j, word, 0); if (flag) { return true; } } } return false; } public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) { if (board[i][j] ! s.charAt(k)) { return false; } else if (k s.length() - 1) { return true; } visited[i][j] true; int[][] directions {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; boolean result false; for (int[] dir : directions) { int newi i dir[0], newj j dir[1]; if (newi 0 newi board.length newj 0 newj board[0].length) { if (!visited[newi][newj]) { boolean flag check(board, visited, newi, newj, s, k 1); if (flag) { result true; break; } } } } visited[i][j] false; return result; }分析 1、代码的时间复杂度为O(m * n * 3^L)其中 M,N 为网格的长度与宽度L 为字符串 word 的长度。空间复杂度为O(m*n)。 2、官方解答的思路与我的解答思路一致故不重复赘述。总结本题只需掌握基础的递归 回溯即可。
