【小马的LeetCode练功坊】leetcode教你解字谜游戏- 79. Word Search,212. Word Search II

最新域名优惠/VPS优惠/免备案CDN活动

嗨嗨,大家好,
今天要介绍的是一道经典问题- 字谜游戏
(见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;
    }
};

推荐:
word press知更鸟主题去授权谁有最新得?可以有偿

米老头大佬: word press知更鸟主题去授权谁有最新得? 目前看到网络上都是2018.2017得。太老了。 可以有偿 或者PM我联系方式。。 zzz123大佬: 又不贵,貌似300块 付费求破戒…

出瓦工18.79

whh大佬: 瓦工18.79,上更好的机场了,不折腾 弃坑了。Monday, January 25th, 2021过期。IP已墙。 带价咨询吧 QQ:798045264 cooe大佬: 算还有9.5个…

20出瓦工年付18.79 cn2,ip正常,今天续费

利物浦大佬: 佛系出吧,出不掉就扔了 似毛非毛大佬: 楼下要了·~ ansheng大佬: 兴趣不大,早出 利物浦大佬: 玩鸡一个月,手里5台鸡了,瓦工失宠了 ansheng大佬: 兴趣不大,早出 yu…

发表评论

电子邮件地址不会被公开。 必填项已用*标注