Leetcode — 79. Word Search (中文)

7 min readJan 5, 2021

問題連結: 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;
    }