力扣 – 劍指 Offer 12. 矩陣中的路徑

• 2021 年 11 月 21 日
• 筆記
• DFS, 剪枝, 回溯, 算法與題解, 遞歸

題目

劍指 Offer 12. 矩陣中的路徑

思路1（回溯、DFS）

• 這題可以使用回溯+遞歸來解決，思路如下：
  1. 將二維數組的每一個元素都作為起點進行回溯查找
  2. 每次查找的時候，都有四個方向，但是上一個方向不能再次被遍歷，因此需要將遍歷過的位置進行做標記，遞歸返回的時候再還原
  3. 遞歸過程中要判斷一些條件：越界直接返回false、當前字符和word中的不匹配也直接返回false
  4. 何時為匹配成功呢？只要能匹配到word的最後一個字符，即curIndex == cs.length-1（curIndex為每次搜索的深度，不過是從0開始的，就是在word中的位置；cs.length-1為最後一個字符的索引位置），因此後面剩下的就不用查找了

代碼

class Solution {
    public boolean exist(char[][] board, String word) {
        char[] cs = word.toCharArray();
        
        // 遍歷整個二維數組，即將每個字符作為第一個字符進行嘗試
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                // 只要有一條符合條件，則返回true
                if (dfs(board, cs, i, j, 0)) {
                    return true;
                }
            }
        }

        // 沒找到
        return false;
    }

    public boolean dfs(char[][] board, char[] cs, int i, int j, int curIndex) {
        // 超過二維數組邊界就返回false
        // 字符不匹配也直接結束遞歸
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != cs[curIndex]) {
            return false;
        }

        // 如果以及全部匹配到了，就直接返回true，而不用繼續匹配剩下的啦
        if (curIndex == cs.length - 1) {
            return true;
        }

        // 能遞歸到這裡，說明當前cs中curIndex索引對應的字符和boards是匹配的
        // 因此我們需要吧遍歷過的字符設置為空白，防止再次遍歷
        board[i][j] = '\0';
        boolean res = dfs(board, cs, i + 1, j, curIndex + 1) ||
                      dfs(board, cs, i - 1, j, curIndex + 1) ||
                      dfs(board, cs, i, j + 1, curIndex + 1) ||
                      dfs(board, cs, i, j - 1, curIndex + 1);
        // 回溯的時候要把原來設置為空白字符的還原
        board[i][j] = cs[curIndex];

        // 只要出現true，就一路返回
        return res;
    }
}

複雜度分析

• 時間複雜度：\(O(MN·3^K)\)，二維數組共有M·N個起點；然後對於每個起點來說，每步都有三個方向可以選擇（不包括上一個方向），最長要走的步數就是word的長度K，因此複雜度為\(3^K\)
• 空間複雜度：\(O(K)\)，遞歸深度最深也就是word的長度