iT邦幫忙

1

【小馬的LeetCode練功坊】leetcode教你解字謎遊戲- 79. Word Search,212. Word Search II

嗨嗨,大家好,
今天要介紹的是一道經典問題- 字謎遊戲
(見wiki- Word search)
相信大家在英文課上多多少少有玩過(?)

先從簡單的一題開始,
參考題目:79. Word Search

給你一個2D的字謎,判斷一個英文單字是否在裡面:
譬如說

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

若是找一個字在不在裡面的話,
相信對程式算法熟悉的話應該不太難,
跑一個DFS就可以解了

79. c++程式(AC)

class Solution {
public:
    bool inBoundary(vector<vector<char>>&board,int pr,int pc){
        return pr>=0 && pr<board.size() && pc>=0 && pc<board[0].size(); 
    }
    
    bool dfs(vector<vector<char>>&board,int pr,int pc,string &word,int count){
        if(count==word.size()-1){
            return true;
        }
        char temp=board[pr][pc];
        board[pr][pc]='.';
        vector<pair<int, int>> directions = {{1,0}, {-1,0}, {0,1}, {0,-1}}; //定義四個方向
        for(auto d: directions){
            int r = pr+d.first, c = pc+d.second;
            if(inBoundary(board, r, c) && board[r][c]==word[count+1]&&dfs(board,r,c,word,count+1)){
                return true;
            }
        }
        board[pr][pc] = temp;
        return false;

    }
    
    bool exist(vector<vector<char>>& board, string word) {
        
        for(int i=0;i<board.size();i++){
            for(int j=0;j<board[0].size();j++){
                if(board[i][j]==word[0] && dfs(board,i,j,word,0)){
                    return true;
                }
            }
        }
        return false;
    }
};

但是類似的一題就難了

字謎搜索多個單字

參考題目:212. Word Search II
一樣給你一個2D的字謎,判斷一堆英文單字是否在裡面
範例:

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"]

注意這邊若用上面一題的DFS程式逐個字搜索會超時

212. c++程式(超時)

class Solution {
public:
    
    bool inBoundary(vector<vector<char>>&board,int pr,int pc){
        return pr>=0 && pr<board.size() && pc>=0 && pc<board[0].size(); 
    }
    
    bool dfs(vector<vector<char>>&board,int pr,int pc,string &word,int count){
        if(count==word.size()-1){
            return true;
        }
        char temp=board[pr][pc];
        board[pr][pc]='.';
        vector<pair<int, int>> directions = {{1,0}, {-1,0}, {0,1}, {0,-1}}; //定義四個方向
        for(auto d: directions){
            int r = pr+d.first, c = pc+d.second;
            if(inBoundary(board, r, c) && board[r][c]==word[count+1]&&dfs(board,r,c,word,count+1)){
                board[pr][pc] = temp;
                return true;
            }
        }
        board[pr][pc] = temp;
        return false;

    }
    
    bool exist(vector<vector<char>>& board, string word) {
        
        for(int i=0;i<board.size();i++){
            for(int j=0;j<board[0].size();j++){
                if(board[i][j]==word[0] && dfs(board,i,j,word,0)){
                    return true;
                }
            }
        }
        return false;
        
    }
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        vector<string> res;
        for(string word: words){
            if(exist(board, word)){
                res.push_back(word);
            }
        }
        return res;
    }
};

因為這個解法可能會做很多重複的事情,
比如說我們搜aaaa,aaab,aaac,aaad這四個字在不在裡面,
當我們搜索前三個字aaa,發現找不到pattern aaa時,
那這四個字當然都不在裡面了,根本不必重複搜

要達到這個效果,
需要用到trie這個結構(資結經典題目: 實作一個Trie (又稱prefix tree、字典樹、前綴樹)),
這邊我們只要trie插入新單字的功能即可

212. c++程式(AC)

再微調原來的dfs就可以做出來(雖說是微調,我也debug了大概二個小時^^")

class Solution {
    class TrieNode {
    public:
        vector<TrieNode *> child; //子節點有a~z共26種可能,初始設為null
        string prefix; //若某點為單字的結尾,記錄該字的prefix
        TrieNode(): prefix(""), child(vector<TrieNode *>(26, NULL)) {};
    };
    
    class Trie {     
    public:
        TrieNode* root; //root為一個空的節點
        /** Initialize your data structure here. */
        Trie(): root(new TrieNode()) {};

        /** Inserts a word into the trie. */
        void insert(string word) {
            TrieNode *p = root;
            for (char c : word) {
                int i = c - 'a';
                if (!p->child[i]){
                    p->child[i] = new TrieNode();
                } 
                p = p->child[i];
            }
            p->prefix = word;
        }
    };
public:
    
    bool inBoundary(vector<vector<char>>&board,int pr,int pc){
        return pr>=0 && pr<board.size() && pc>=0 && pc<board[0].size(); 
    }
    
    void dfs(vector<vector<char>>&board, TrieNode* trie, int pr,int pc, vector<string> &res){
        if(!trie->prefix.empty()){
            res.push_back(trie->prefix);
            trie->prefix = ""; //避免同一個字重複加到res裡
        }
        char temp=board[pr][pc];
        board[pr][pc]='.';
        vector<pair<int, int>> directions = {{1,0}, {-1,0}, {0,1}, {0,-1}}; //定義四個方向
        for(auto d: directions){
            int r = pr+d.first, c = pc+d.second;
            if(inBoundary(board, r, c) && board[r][c]!='.' && trie->child[board[r][c] - 'a']){
                dfs(board, trie->child[board[r][c] - 'a'], r, c, res);
            }
        }
        board[pr][pc] = temp;

    }
    
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        vector<string> res;
        Trie wordTrie;
        for(string word: words){
            wordTrie.insert(word);
        }
        for(int i=0;i<board.size();i++){
            for(int j=0;j<board[0].size();j++){
                if (wordTrie.root->child[board[i][j] - 'a']) {
                    dfs(board, wordTrie.root->child[board[i][j] - 'a'], i, j, res);
                }
            }
        }
        return res;
    }
};

尚未有邦友留言

立即登入留言