[LeetCode] 79. Word Search

79. Word Search

• Hardness: \(\color{orange}\textsf{Medium}\)
• Ralated Topics: Array、Backtracking、Matrix

一、題目

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”,“d”]], words = [“abcb”]
• 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?

二、分析

• 這題是 [LeetCode] 212. Word Search II 的基本題，是 google 愛考的題型，先考你一題基礎題型，再看你能不能進一步微調。如先考最短路徑的「步數」，再考你最短路徑的「路徑」，此種題型容易藏細節，如最短路徑「步數」可以用 bfs，當走到終點立即回傳，但當考題改成路徑時，就不能立即回傳，因為有可能會有多個最短路徑。
• 這題有許多剪枝技巧：
  1. word 的字長不可能大於 board 的總字數，即 m x n。
  2. word 個別的字數需小於 board 各別的字數。
  3. word 如果是重複的字元組成，則重複的字元擺在尾巴可以有分枝的效果。
     • 即 aaaaaaabc 可以處理成，找 cbaaaaaaa。
• 注意在 search 中回傳 bool 值前，要記得將 backtrack 走完，以免影響其它組解。

三、解題

1. Backtracking

• Time complexity: \(O(m\times n\times l)\)，\(m \) 為 board.size()，\(n\) 為 board[0].size()，\(l\) 為 word.length()
• Space complexity: \(O(m\times n)\)

class Board {
private:
    vector<vector<char>> board;
    int m, n;
    int cnt[128];

    // 用於上、下、左、右
    int dirc[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};

    // 用於剪枝1與剪枝2，在進行算法前，檢查其是否可能為錯，時間複雜度為 O(1)，所以可以大大降低耗時。
    bool isWordNumValid(string& word) {
        if (word.length() > m * n) return false;    // 剪枝1
        int charNum[128] = {0};
        for (char c : word) charNum[c]++;
        for (int i = 0; i < 128; i++) {
            if (charNum[i] > cnt[i]) return false;  // 剪枝2
        }
        return true;
    }

    void reverseIfNeeded(string& word) {
        int left = word.find_first_not_of(word[0]);     // 左邊重複
        int right = word.length() - word.find_last_not_of(word[word.length()-1]);       // 右邊重複
        if (left > right) reverse(word.begin(), word.end());    // 左邊重複較長，則翻轉字串
    }

    bool backtrack(string& word, int row, int col, int i) {
        if (i == word.length()) return true;        // 到達終止條件，回傳 true
        if (row < 0 || col < 0 || row >= m || col >= n || board[row][col] != word[i]) return false;     // out of bound 或不符合
        char tmp = board[row][col];     // 記錄原本的格子
        board[row][col] = '#';          // 用 '#' 代表 visited，省去另外創一個 visited 來記錄是否拜訪過
        for (const auto& d : dirc)
            if (backtrack(word, row+d[0], col+d[1], i+1)) {
                // board[row][col] = tmp;      // 記得將 backtrack 更動的部分走完，以免影響其它組解
                return true;
            }
        board[row][col] = tmp;          // 還原格子
        return false;
    }
    
public:
    Board(vector<vector<char>>& board_) {
        this->board = board_;
        this->m = board_.size();
        this->n = board_[0].size();
        memset(cnt, 0, sizeof(cnt));
        for (const auto& row : board) {
            for (char c : row) {
                cnt[c]++;
            }
        }
    }
    bool search(string& word) {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!isWordNumValid(word)) return false;
                reverseIfNeeded(word);
                if (backtrack(word, i, j, 0)) return true;
            }
        }
        return false;
    }
};
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        Board b(board);
        return b.search(word);
    }
};

回目錄 Catalog