女人18片毛片60分钟免费,亚洲国产AV中文,91泡芙,人人摸人人搞,91蝌蚪91,欧美就是色,国产第一福利,亚洲欧美成人图片

算法的重要性，我就不多說(shuō)了吧，想去大廠，就必須要經(jīng)過(guò)基礎(chǔ)知識(shí)和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個(gè)公眾號(hào)后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問(wèn)題叫做 添加與搜索單詞，我們先來(lái)看題面：

https://leetcode-cn.com/problems/design-add-and-search-words-data-structure/

Design a data structure that supports adding new words and finding if a string matches any previously added string.

題意

請(qǐng)你設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)，支持添加新單詞和查找字符串是否與任何先前添加的字符串匹配。

實(shí)現(xiàn)詞典類(lèi) WordDictionary ：

WordDictionary() 初始化詞典對(duì)象
void addWord(word) 將 word 添加到數(shù)據(jù)結(jié)構(gòu)中，之后可以對(duì)它進(jìn)行匹配
bool search(word) 如果數(shù)據(jù)結(jié)構(gòu)中存在字符串與 word 匹配，則返回 true ；否則，返回 false 。word 中可能包含一些 '.' ，每個(gè) . 都可以表示任何一個(gè)字母。

示例

輸入：
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
輸出：
[null,null,null,null,false,true,true,true]

解釋?zhuān)?br mpa-from-tpl="t">WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True
 

提示：
1 <= word.length <= 500
addWord 中的 word 由小寫(xiě)英文字母組成
search 中的 word 由 '.' 或小寫(xiě)英文字母組成
最多調(diào)用 50000 次 addWord 和 search

解題

用字典樹(shù)來(lái)作為存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)。

新增單詞的時(shí)候，就使用字典樹(shù)插入新單詞的方法。

在查找某一個(gè)字典樹(shù)時(shí)，使用深度優(yōu)先搜索即可。

class WordDictionary {
public:
    //定義字典樹(shù)中每個(gè)節(jié)點(diǎn)的結(jié)構(gòu)
    struct Node{
        bool isword = false; //用于標(biāo)記當(dāng)前節(jié)點(diǎn)是否為單詞的最后一個(gè)字符
        Node* next[27] = {};
    };
    Node* root; //每一個(gè)class都有一棵字典樹(shù)
    /** Initialize your data structure here. */
    WordDictionary() {
        root = new Node(); //新建一棵字典樹(shù)
    }
    
    /** Adds a word into the data structure. */
    void addWord(string word) {
        Node* tmp = root;
        for(auto w: word){
            if(tmp->next[w - 'a'] == NULL){ //還沒(méi)有這個(gè)節(jié)點(diǎn)
                Node* tt = new Node();
                tmp->next[w - 'a'] = tt; //那就新建節(jié)點(diǎn)
            }
            tmp = tmp->next[w - 'a'];
        }
        tmp->isword = true; //遍歷完一個(gè)單詞
    }
    
    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    bool search(string word) {
        return dfs(word, root, 0);
    }
    
    bool dfs(string word, Node* root, int i){
        if(!root) return false;
        if(i >= word.size()) return root->isword; //看看是不是一個(gè)完整的單詞
        if(word[i] != '.'){
            if(root->next[word[i] - 'a']){
                return dfs(word, root->next[word[i] - 'a'], i+1);
            }
            else return false;
        }
        for(auto t: root->next){
            if(t){
                if(dfs(word, t, i+1)) return true;
            }
        }
        return false;
    }
};