力扣211. 添加与搜索单词 - 数据结构设计-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣211. 添加与搜索单词 - 数据结构设计。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

字典树

思路：
- 设计一棵字典树，每个节点存放单词的一个字符，节点放一个标记位，如果是单词结束则标记；
- 字典树插入：
  - 字典树默认有 26 个 slot 槽代表 a - z；
  - 遍历单词，如果字符对应槽存在则迭代到子节点，如果不存在则创建；
  - 在单词结尾的节点，将 flag 标记；
- 字典树查询：
  - 定义 dfs(word, index, trie) 函数，表示 word 的第 index 字符是否在 trie 树上；
  - 递归查询，终止条件为 index 为 word 长度，并且 flag 标记被设置；
  - 需要注意通配符 '.'，代表任意字母:
    - } else if (c == '.') {
    - for (int i = 0; i < 26; i++) {
    - TrieNode* child = node->child[i];
    - if (child != nullptr && dfs(word, index + 1, child)) {
    - return true;
    - }
    - }
    - }
完整代码：

struct TrieNode {
    std::vector<TrieNode*> child;
    bool isEnd;

    TrieNode() :
      child(std::vector<TrieNode*>(26, nullptr)) ,
      isEnd(false) {
    }

};

void insert(TrieNode* root, const std::string& word) {
    TrieNode* node = root;
    for (auto c : word) {
        if (node->child[c - 'a'] == nullptr) {
            node->child[c - 'a'] = new TrieNode();
        }
        node = node->child[c - 'a'];
    }
    node->isEnd = true;
}

class WordDictionary {
public:
    WordDictionary() {
        tire = new TrieNode();
    }
    
    void addWord(string word) {
        insert(tire, word);
    }
    
    bool search(string word) {
        return dfs(word, 0, tire);
    }

private:
    bool dfs(const std::string& word, int index, TrieNode* node) {
        if (index == word.size()) {
            return node->isEnd;
        }

        char c = word[index];
        if (c >= 'a' && c <= 'z') {
            TrieNode* child = node->child[c - 'a'];
            if (child != nullptr && dfs(word, index + 1, child)) {
                return true;
            }
        } else if (c == '.') {
            for (int i = 0; i < 26; i++) {
                TrieNode* child = node->child[i];
                if (child != nullptr && dfs(word, index + 1, child)) {
                    return true;
                }
            }
        }

        return false;
    }

private:
    TrieNode* tire;
};

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