LCR 129. 字母迷宮

LCR 129. 字母迷宮

參考題解：靈神題解

解題思想

首先我們知道該題需要枚舉i=0,1,2,...,n-1，j = 0,1,2,3,...,m-1，以(i,j)為起點開始搜索

同時我們還需要知道target匹配到了哪個字符，定義一個記錄參數k

定義一個dfs(i, j, k)深度搜索函數表示當前這個格子，是否匹配target(k)，匹配返回true，否則false

對于dfs(i,j,k)分類討論：

• 如果grid[i,j]不等于target[k]，返回false
• 如果參數k等于target的長度 - 1，即k=len(target)-1，返回true
• 枚舉(i,j)的相鄰的四個格子(x,y)，如果(x,y)沒有出界，則遞歸dfs(x,y,k+1)，如果返回true，那么dfs(i,j,k)就一定也是true
• 如果四個相鄰格子都是false，那就返回false

避免重復訪問細節

為了避免重復訪問同一個格子，可以使用vis數組標記每一個訪問過的字符，但是更方便的可以直接將grid[i,j]先設為0，如果返回false直接恢復現場，返回true就不用恢復現場，因為已經匹配到了

代碼展示：

public boolean dfs( int i, int j, int k, char[][] grid, char[] target) {
        // 字符串數組的字符和 target 中的不匹配
        if(grid[i][j] != target[k]) {
            return false;
        }
        // 成功匹配記錄數字 k 的值等于 target 的長度
        if(k == target.length - 1) {
            return true;
        }
        grid[i][j] = 0; // 標記訪問過
        for(int[] d: DIRS) {
            int x = i + d[0];
            int y = j + d[1];
            if(0 <= x && x <= grid.length - 1 && 0 <= y && y <= grid[x].length - 1 && dfs(x, y, k + 1, grid, target)) {
                return true; // 成功搜到
            }
        }
        // 沒搜到
        grid[i][j] = target[k]; // 恢復現場
        return false;
    }

可優化的點

優化1

如果grid中的某個字符出現的次數比target中對應的字符出現的次數大，返回false

// 優化1
char[] t = target.toCharArray();
int[] targetCnt = new int[128];
for(int c: t) {
    if(++targetCnt[c] > cnt[c]) {
        return false; // grid 某個字符和 target 對應的字符出現次數不符
    }
}

優化2

假設target的首字符出現的次數為x，末尾字符出現的次數為y，如果x > y，那么就將target反轉，這樣在一開始就滿足了grid[i][j] != target[k]，不用接著往后搜索了

// 優化 2
if(cnt[t[t.length - 1]] < cnt[t[0]]) {
    t = new StringBuilder(target).reverse().toString().toCharArray();
}

最終代碼展示

class Solution {
    private static final int[][] DIRS = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
    public boolean wordPuzzle(char[][] grid, String target) {
        // 用數組代替哈希表
        int[] cnt = new int[128];
        for (char[] row : grid) {
            for (char c : row) {
                cnt[c]++; // 將cnt[c]的值加1，做好 key-value
            }
        }

        // 優化1
        char[] t = target.toCharArray();
        int[] targetCnt = new int[128];
        for(int c: t) {
            if(++targetCnt[c] > cnt[c]) {
                return false; // grid 某個字符和 target 對應的字符出現次數不符
            }
        }

        // 優化 2
        if(cnt[t[t.length - 1]] < cnt[t[0]]) {
            t = new StringBuilder(target).reverse().toString().toCharArray();
        }


        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[i].length; j++) {
                if(dfs(i, j, 0, grid, t)) {
                    return true; // 搜到了
                }
            }
        }
        return false;
    }

    public boolean dfs( int i, int j, int k, char[][] grid, char[] target) {
        // 字符串數組的字符和 target 中的不匹配
        if(grid[i][j] != target[k]) {
            return false;
        }
        // 成功匹配記錄數字 k 的值等于 target 的長度
        if(k == target.length - 1) {
            return true;
        }
        grid[i][j] = 0; // 標記訪問過
        for(int[] d: DIRS) {
            int x = i + d[0];
            int y = j + d[1];
            if(0 <= x && x <= grid.length - 1 && 0 <= y && y <= grid[x].length - 1 && dfs(x, y, k + 1, grid, target)) {
                return true; // 成功搜到
            }
        }
        // 沒搜到
        grid[i][j] = target[k]; // 恢復現場
        return false;
    }
}