首页 > 代码库 > [leetcode]Word Search

[leetcode]Word Search

2024-07-12 03:58:51   214人阅读

Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[  ["ABCE"],  ["SFCS"],  ["ADEE"]]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

 

时隔这么久，第二遍刷，居然跟第一遍的代码完全一样，连细节都一样，太不可思议了。

算法思路：

对上下左右四个方向进行递归，dfs，注意判断边界

 1 public class Solution { 2      public boolean exist(char[][] board, String word) { 3          if(board == null || board.length == 0|| word == null ) return false; 4          int height = board.length; 5          int width = board[0].length; 6          if(height * width < word.length()) return false; 7          for(int i = 0; i < height; i++){ 8              for(int j = 0; j < width; j++){ 9                  if(board[i][j] == word.charAt(0)){10                      if(dfs(board,word.substring(1),i,j)) return true;11                  }12              }13          }14          return false;15      }16      private boolean dfs(char[][] board,String left,int row,int column){17          if(left.length() == 0){18              return true;19          }20          int height = board.length;21          int width = board[0].length;22          char c = board[row][column];23          board[row][column] = ‘ ‘;24          if( column > 0 && board[row][column - 1] == left.charAt(0)){//go left25              if( dfs(board, left.substring(1), row, column - 1)) return true;26          }27          if( column < width - 1 && board[row][column + 1] == left.charAt(0)){//go right28              if( dfs(board, left.substring(1), row, column + 1)) return true;29          }30          if( row > 0 && board[row - 1][column] == left.charAt(0)){//go up31              if( dfs(board, left.substring(1), row - 1, column) ) return true;32          }33          if( row < height - 1 && board[row + 1][column] == left.charAt(0)){//go down34              if( dfs(board, left.substring(1), row + 1, column)) return true;35          }36          board[row][column] = c;37          return false;38      }39 }

其实这道题这种做法是不严谨的，因为题中并未说明字符串中不包含空格，事实上最好开辟一个标记矩阵，来标记哪些点是否已经匹配过。

我的算法中对上下左右四个方向进行了直接的判断，我同学的做法，用一个数组来标记走向，很值得借鉴。戳这里。

 


联系
我们