欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【leetcode】211. Add and Search Word - Data structure design

程序员文章站 2022-05-18 10:04:08
...

题目:
【leetcode】211. Add and Search Word - Data structure design


思路:
数据结构与【leetcode】208. Implement Trie (Prefix Tree)是一样的,只是search函数从迭代的方式改成了递归的方式,因为遇到字符“.”会涉及到回溯。

我又对此数据结构的存储细节进行了剖析,以“dad”为例,其的存储结构如下图:
【leetcode】211. Add and Search Word - Data structure design


代码实现:

class TrieNode{
public:
    TrieNode *child[26];
    TrieNode():isWord(false){
        for (auto &a : child){
            a = nullptr;
        }
    }
    bool isWord; // 如果此节点最后一个字符,则说明到此为止是一个完整的单词。
};

class WordDictionary {
private:
    TrieNode *root;    
public:
    /** Initialize your data structure here. */
    WordDictionary() {
        root = new TrieNode();
    }
    
    /** Adds a word into the data structure. */
    void addWord(string word) {
        TrieNode *p = root;
        for (auto &c : word){
            int i = c - 'a';
            if (p->child[i] == nullptr){
                p->child[i] = new TrieNode();
            }
            p = p->child[i];
        }
        p->isWord = true;
    }
    
    /** 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 f(word, 0, root);
    }
    
    bool f(string &word, int w_i, TrieNode* p){
        if (w_i >= word.size()){
            return p->isWord;
        }
        
        if (word[w_i] == '.'){
            for (int i = 0; i < 26; ++i){
                if (p->child[i]){
                    if (f(word, w_i+1, p->child[i])){
                        return true;
                    }
                }
            }
        }else{
            if (p->child[word[w_i]-'a'] == nullptr){
                return false;
            }
            return f(word, w_i+1, p->child[word[w_i]-'a']);
        }
        
        return false;
    }
    
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary* obj = new WordDictionary();
 * obj->addWord(word);
 * bool param_2 = obj->search(word);
 */