212. Word Search II

  • Hardness: \(\color{red}\textsf{Hard}\)
  • Ralated Topics: Array、String、Backtracking、Trie、Matrix

一、題目

Given an m x n board of characters and a list of strings words, return all words on the board.
Each word must 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 in a word.

Example 1:

  • Input: board = [[“o”,“a”,“a”,“n”],[“e”,“t”,“a”,“e”],[“i”,“h”,“k”,“r”],[“i”,“f”,“l”,“v”]], words = [“oath”,“pea”,“eat”,“rain”]
  • Output: [“eat”,“oath”]

Example 2:

  • Input: board = [[“a”,“b”],[“c”,“d”]], words = [“abcb”]
  • Output: []

Example 3:

  • Input:
  • Output:

Constraints:

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 12
  • board[i][j] is a lowercase English letter.
  • 1 <= words.length <= 3 * 104
  • 1 <= words[i].length <= 10
  • words[i] consists of lowercase English letters.
  • All the strings of words are unique.

二、分析

  • 這題是 [LeetCode] 79. Word Search 的進階題，是 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[26];

    // 用於上、下、左、右
    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[26] = {0};
        for (char c : word) charNum[c-'a']++;
        for (int i = 0; i < 26; 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-'a']++;
            }
        }
    }
    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:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        Board b(board);
        vector<string> res;
        for (const auto& word : words) {
            if (b.search(word)) res.push_back(word);
        }
        return res;
    }
};

回目錄 Catalog