一步步将dfs回溯剪枝進行優化(LeetCode 79. 單詞搜尋)

一個極其普通的解法

主要思想是找到可行的起始點 深度周遊搜尋 儲存目前的字元串如果比對則繼續否則剪枝

class Solution {
    char[][] board;
    boolean res = false;
    int n;
    int m;
    boolean[][] visited;
    public boolean exist(char[][] board, String word) {
        this.board = board;
        n = board.length;
        m = board[0].length;
        visited = new boolean[n][m];
        char c = word.charAt(0);
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(c == board[i][j]){
                    dfs(i,j,"",word);
                    if(res == true)return true;
                }
            }
        }
        return false;
    }
    public void dfs(int row,int column,String cur,String word){
        if(column == -1 || row == -1 || column == m || row == n)return;
        if(visited[row][column]) return;
        cur += board[row][column];
        int length = cur.length();
        if(word.charAt(length - 1) != cur.charAt(length - 1))return;
        if(word.length() == cur.length()) {
            res = true;
            return;
        }
        visited[row][column] = true;
        dfs(row,column + 1,cur,word);
        dfs(row,column - 1,cur,word);
        dfs(row + 1,column,cur,word);
        dfs(row - 1,column,cur,word);
        visited[row][column] = false;  
    }
}      

這就是我第一次送出的代碼 來看看執行效率

額… 看來這個方案還是有不少優化的餘地的 讓我們接着往下看

考慮中間過程

在學習動态規劃的時候我們知道，很多題目其實隻求最終的答案 這種時候我們不必存儲中間過程

除非中間過程是一些你要多次求解的資料 此時緩存下來才是對提高時間效率有幫助的

在這裡也是，我們沒有必要把目前求得的整個字元串存儲下來，我們隻需要判斷目前的相應位置字元是否比對即可，是以引出優化一：省略中間過程

優化一：省略中間過程

//隻判斷目前位置就好啦 不符合就剪枝
        if(word.charAt(curCount) != board[row][column])return;      

class Solution {
    char[][] board;
    boolean res = false;
    int n;
    int m;
    boolean[][] visited;
    public boolean exist(char[][] board, String word) {
        this.board = board;
        n = board.length;
        m = board[0].length;
        visited = new boolean[n][m];
        char c = word.charAt(0);
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(c == board[i][j]){
                    dfs(i,j,0,word);
                    if(res == true)return true;
                }
            }
        }
        return false;
    }
    public void dfs(int row,int column,int curCount,String word){
        if(column == -1 || row == -1 || column == m || row == n)return;
        if(visited[row][column]) return;
        //隻判斷目前位置就好啦 不符合就剪枝
        if(word.charAt(curCount) != board[row][column])return;
        if(word.length() - 1 == curCount) {
            res = true;
            return;
        }
        visited[row][column] = true;
        dfs(row,column + 1,curCount + 1,word);
        dfs(row,column - 1,curCount + 1,word);
        dfs(row + 1,column,curCount + 1,word);
        dfs(row - 1,column,curCount + 1,word);
        visited[row][column] = false;  
    }
}      

時間和空間效率都大大地提升，主要原因是不需要存儲大量的中間字元串，以及省去了對字元串進行操作的時間成本

考慮visited數組

visited數組是我定義的記錄目前位置的布爾數組，這個能不能也想辦法把它省去呢？這裡對二維數組的存儲和操作也是需要一些成本的

在沒有提供原始數組的題目中(如求1…n的排列的所有組合)，我們确實沒辦法，隻能手動定義visited數組，但在本題可是有存儲單詞字母的二維數組的，我們把這個原始數組利用起來就可以省去visited數組的成本！是以引出優化二：省略visited數組

優化二：省略visited數組

這個時候題目的提示資訊的重要性就展現出來了

既然原始數組僅由字母組成，那麼我們用一個符号"."來表示這個位置已經通路過不能再次使用不就好了？

不過記得儲存原始狀态然後在dfs之後恢複

char c = board[row][column];
board[row][column] = '.';

//dfs....

board[row][column] = c;      

class Solution {
    char[][] board;
    boolean res = false;
    int n;
    int m;
    char[] arr;
    public boolean exist(char[][] board, String word) {
        this.board = board;
        n = board.length;
        m = board[0].length;
        
        arr = word.toCharArray();
        char c = word.charAt(0);
        //找合适的起始點
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(c == board[i][j]){
                    dfs(i,j,0);
                    if(res == true)return true;
                }
            }
        }
        return false;
    }
    public void dfs(int row,int column,int cur){
        //判斷範圍
        if(column == -1 || row == -1 || column == m || row == n || cur == arr.length)return;
        //判斷是否已通路 是否比對 剪枝
        if(arr[cur] != board[row][column]) return;
        if(cur == arr.length - 1) {
            res = true;
            return;
        }
        char c = board[row][column];
        board[row][column] = '.';
        dfs(row,column + 1,cur+1);
        dfs(row,column - 1,cur+1);
        dfs(row + 1,column,cur+1);
        dfs(row - 1,column,cur+1);
        board[row][column] = c;  
    }
}