Leetcode — 79. Word Search (中文)

問題連結: https://leetcode.com/problems/word-search/

給予一個m x n 的二維陣列board 以及一個字串 word
在陣列中, 我們可以從水平或垂直方向連成一個字串(也就是可以上下左右去traverse陣列), 且連成字串的途中不能再重複使用已連過的字元
題目要求回傳我們能不能在board中找到word的存在

限制:

• m == board.length
• n = board[i].length
• 1 <= m, n <= 200
• 1 <= word.length <= 103
• board 和word 保證只包含英文大小寫字母

範例 
Input: board = 
[["A","B","C","E"],
 ["S","F","C","S"],
 ["A","D","C","E"]], 
word = "ABCCCD"
Output: true 
(我們可以從 (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (2,1) 連成我們想要找的word)

想法:

因為這題題目感覺如果不自己組成所有可能的連法, 就不能解出來, 那感覺可以用backtracking來幫我們找所有可能的選擇以及之後的路

用backtracking代表我們要一直不停的做選擇, 直到某一選擇不能再選了我們再重新回去上次做選擇的地方,做另一個選擇,..持續下去

讓我們來用圖來解釋我們要如何解上述的範例 我們其實在每個位置都需要做backtracking, 來看從某一位置開始 可以連成的各種字串組合
這題我們需要做兩次backtracking, 因為只有兩格是A, 符合我們word的開頭字母
因為篇幅有限 我只會介紹我們如何在起點為(0,0)時 開始做backtracking 另一個位置(2,0)大家也可以自己試試 基本上邏輯都一樣

👉Goal: Find ABCCCD in [ [A, B, C, E], [S, F, C, S], [A, D, C, E] ]

Step 1. 我們已決定從(0,0)開始我們的旅程 (也就是我們的第一個選擇)
下一個選擇就是要看我們要往哪個方向走 (💡下個目標: 連成 BCCCD)

Step 2. 因為只有(0,1) 有符合字首條件. 我們決定下一步就是往右走(💡下個目標: 連成 CCCD)

Step 3. 只有 (0,2)的字首為C. 繼續往右連 (💡下個目標: 找到 CCD)

Step 4. 只有 (1,2)的字首為C. 這次往下連(💡下個目標: 找到 CD)

Step 5. 這次雖然往上走(0,2)跟往下走(2,2)的字母都是C, 但我們因為走過(0,2)了, 題目要求一格只能走一次, 所以我們這次也只有一個選擇, 只能往下走. (💡下一目標: 找到 D)

Step 6. 只有(2,1) 是字母D, 選擇往左 (💡沒有字母需要再繼續連了, 完成!)

以下為我的 9ms 程式碼, 只贏過 29%:

public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        char firstW = word.charAt(0);
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if( board[i][j]!=firstW )
                    continue;
                if( helper( board, i, j, word.toCharArray()
                    , 0, new boolean[m][n]) )
                    return true;
            }
        }
        return false;
    }
    public boolean helper(char[][] board,int i,int j,char[] words, int indx, boolean[][] visited){
        if( indx >= words.length)
            return true;
        if( i<0 || j<0 || i>=board.length || j>=board[i].length
            ||board[i][j]!=words[indx]|| visited[i][j])
            return false;
        visited[i][j] = true; //make the choice
        if( helper(board,i+1,j,words,indx+1,visited)
           || helper(board,i,j+1,words,indx+1,visited)
           || helper(board,i-1,j,words,indx+1,visited)
           || helper(board,i,j-1,words,indx+1,visited) )
            return true;
        visited[i][j] = false; // undo the choice
        return false;
    }

📝 一個改善上述程式碼的小提示 — 在上述程式碼, 我們用二維的boolean陣列來記錄我們有沒有連過特定的cells, 但我們其實可以利用題目給的另一個條件 "題目給的二維陣列只包含英文字母" 來省掉這個步驟

因為我們現在沒有另一個二維陣列來記錄有沒有traverse過某個位置, 我們可以做的就是 暫時性的改掉我們經過過的字母, 在找到 選擇這個位置後的所有可能性後, 再把字母放回去(也就是backtracking中的undo, 重新選另一個選擇的動作)

以下就是3ms的程式碼, 因此而贏過99%:

public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        char firstW = word.charAt(0);
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if( board[i][j]!=firstW )
                    continue;
                if( helper(board, i, j, word.toCharArray(), 0) )
                    return true;
            }
        }
        return false;
    }
    public boolean helper(char[][] board,int i,int j,char[] words, int indx){
        if( indx >= words.length)
            return true;
        if(i<0 || j<0 || i>=board.length || j>=board[i].length
           || board[i][j] != words[indx])
            return false;
        char c = board[i][j];
        board[i][j] = '.'; //temporarily modify the value
        if( helper(board,i+1,j,words,indx+1)
           || helper(board,i,j+1,words,indx+1)
           || helper(board,i-1,j,words,indx+1)
           || helper(board,i,j-1,words,indx+1) )
            return true;
        board[i][j] = c; //recover
        return false;
    }

因為我們在程式中嘗試找出所有可能的選擇組合 時間複雜度為指數級的高.