在字符网格中搜索单词

Question

我正在处理leetcode 问题。我想出了以下简单的解决方案，但它给出了错误的输出。

给定一个 2D 板和一个单词，查找该单词是否存在于网格中。

单词可以由顺序相邻的单元格的字母构成，其中“相邻”单元格是水平或垂直相邻的单元格。同一个字母单元格不能多次使用。

对于此输入：

板：[["a","b"],["c","d"]]

词：“abcd”

它应该返回false，但下面的解决方案返回true。

public static boolean exist(char[][] board, String word) {
    int row = board.length;
    int col = board[0].length;
    Map<Character, Integer> hm = new HashMap<Character, Integer>();
    for (int i = 0; i < row; i++) {
      for (int j = 0; j < col; j++) {
        hm.put(board[i][j], hm.getOrDefault(board[i][j], 0) + 1);
      }
    }

    char[] words = word.toCharArray();
    for (int i = 0; i < words.length; i++) {
      char x = words[i];
      if (hm.containsKey(x) && hm.get(x) > 0)
        hm.put(x, hm.get(x) - 1);
      else
        return false;
    }
    return true;
  }

Answer 1

使用 DFS（深度优先搜索）算法：

public boolean exist(char[][] board, String word) {
    int m = board.length;
    int n = board[0].length;

    boolean result = false;
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
           if(dfs(board,word,i,j,0)){
               result = true;
           }
        }
    }

    return result;
}

public boolean dfs(char[][] board, String word, int i, int j, int k){
    int m = board.length;
    int n = board[0].length;

    if(i<0 || j<0 || i>=m || j>=n){
        return false;
    }

    if(board[i][j] == word.charAt(k)){
        char temp = board[i][j];
        board[i][j]='#';
        if(k==word.length()-1){
            return true;
        }else if(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)){
            return true;
        }
        board[i][j]=temp;
    }

    return false;
}