LeetCode: 79-Word Search 解題紀錄

Last Updated on 2022-11-24 by Clay

題目

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Example 2:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Example 3:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false

Constraints:

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board and word consists of only lowercase and uppercase English letters.

Follow up: Could you use search pruning to make your solution faster with a larger board?

題目給定一個棋盤空間以及一組文字，我們要判斷的就是文字是否有出現在棋盤上。當然，我們不能走重複的位置。

---

解題紀錄

這題我的解法是很純粹地用 DFS 下去解，不過雖然在 C++ 時通過了、但是在 Python 時卻超過時限… 可能有哪邊需要改進。

DFS 遞迴式裡，第一個要判斷的是文字 word 是否已經判斷到最後一個字元了。如果已經判斷到最後一個字元，則回傳 true。

接著是判斷當前棋盤上要判斷的點，是否超出了邊界。

最後，則是判斷棋盤上當前要判斷的文字，跟當前要匹配的文字 word 中的字元是否一致。

C++ 範例程式碼

class Solution {
public:
    bool dfs(vector<vector<char>>& board, string word, int i, int j, int k) {
        // If matching is finished
        if (k >= word.size()) {
            return true;
        }
        
        // If current position (i, j) is out of boundary
        if (i < 0 || j < 0 || i >= board.size() || j >= board[0].size()) {
            return false;
        }
        
        // If the current character is mismatch the word
        if (board[i][j] != word[k]) {
            return false;
        }
        
        // Change the current board to prevent the DFS check the same character again 
        char temp = board[i][j];
        board[i][j] = 0;
        
        // DFS
        bool isExisted = dfs(board, word, i+1, j, k+1) || dfs(board, word, i-1, j, k+1) || dfs(board, word, i, j+1, k+1) || dfs(board, word, i, j-1, k+1);
        
        // Recovery
        board[i][j] = temp;
        
        return isExisted;
    }
    
    bool exist(vector<vector<char>>& board, string word) {
        // Iter
        for (int i=0; i<board.size(); ++i) {
            for (int j=0; j<board[0].size(); ++j) {                
                if (dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        
        return false;
    }
};

---

References

• 79. Word Search

---

Read More

• LeetCode 解題紀錄目錄