【leetcode】單詞搜尋

題目：

給定一個二維網格和一個單詞，找出該單詞是否存在于網格中。

單詞必須按照字母順序，通過相鄰的單元格内的字母構成，其中“相鄰”單元格是那些水準相鄰或垂直相鄰的單元格。同一個單元格内的字母不允許被重複使用。

示例:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

給定 word = "ABCCED", 傳回 true
給定 word = "SEE", 傳回 true
給定 word = "ABCB", 傳回 false      

提示：

• board

   和 

  word

   中隻包含大寫和小寫英文字母。

• 1 <= board.length <= 200

• 1 <= board[i].length <= 200

• 1 <= word.length <= 10^3

思路：

使用dfs+回溯法，從每一個點出發進行探索，看指定word是否出現。

有一個與board次元相同的viewed數組用于記錄探索路徑，為true即為該位置是一個探索路徑。

必要的剪枝政策。

1、數組越界

2、該節點已經通路過

3、index位置的字元與字元串中的字元不符

java代碼：

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

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                boolean res = existDfs(board, word, viewed, i, j, 0);
                if (res) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean existDfs(char[][] board, String word, boolean[][] viewed, int row, int col, int index) {
        //index表示的是目前探索的是第幾個詞 
        if (row < 0 || row >= board.length || col < 0 || col >= board[0].length ||
                viewed[row][col] || board[row][col] != word.charAt(index)) {
            return false;
        }

        index++;
        if (index == word.length()) {
            //word所有字元均比對上
            return true;
        }

        viewed[row][col] = true;
        //注意index已經++
        boolean right = existDfs(board, word, viewed, row + 1, col, index);
        boolean left = existDfs(board, word, viewed, row - 1, col, index);
        boolean up = existDfs(board, word, viewed, row, col - 1, index);
        boolean down = existDfs(board, word, viewed, row, col + 1, index);
        if(right||left||up||down) {
            return true;
        }else {
            viewed[row][col] = false;
            return false;
        }
    }
}
           

由于水準有限，部落格中難免會有一些錯誤，有纰漏之處懇請各位大佬不吝賜教！

推薦閱讀：

【leetcode】子集

【leetcode】全排列

【leetcode】括号生成

【leetcode】電話号碼的字母組合

【leetcode-動态規劃】爬樓梯  - CSDN部落格

【leetcode-動态規劃】買賣股票的最佳時機  - CSDN部落格

【leetcode-動态規劃】最大子序和 

【leetcode-動态規劃】 不同路徑  - CSDN部落格

【leetcode-動态規劃】打家劫舍  

及時更新最新文章和學習資料，一起來學習：