LeetCode 题解

积跬步，至千里。

添加与搜索单词 - 数据结构设计

分类：LeetCode 标签： 设计 字典树 回溯算法 发布于：2019-10-20 ID：211

题目描述

来源于 https://leetcode-cn.com/

设计一个支持以下两种操作的数据结构：

void addWord(word)
bool search(word)

search(word) 可以搜索文字或正则表达式字符串，字符串只包含字母 . 或 a-z 。 . 可以表示任何一个字母。

示例:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

说明:

你可以假设所有单词都是由小写字母 a-z 组成的。

解法：

解法一：字典树

class WordDictionary {
public:
    struct Node;
    struct Node{
        Node():tail(false){}
        bool tail;
        shared_ptr<Node> next['z'-'a'+1];
    };


    WordDictionary() {
        root = make_shared<Node>();
    }

    /** Returns if the word is in the trie. */
    bool search(string word) {
        return dfs(root, word, 0);
    }

    /** Adds a word into the data structure. */
    void addWord(string word) {
        shared_ptr<Node> p = root;
        for(char ch : word){
            int index = ch - 'a';
            if(p->next[index] == nullptr){
                p->next[index] = make_shared<Node>();
            }
            p = p->next[index];
        }
        p->tail = true;
    }

private:
    bool dfs(shared_ptr<Node> node, const string &word, size_t i){
        if(i == word.size()){
            return node->tail;
        }

        char ch = word[i];
        if(ch == '.'){
            for(const auto& p: node->next){
                if(p != nullptr && dfs(p, word, i+1)){
                    return true;
                }
            }
            return false;
        }else{
            int index = ch - 'a';
            if(node->next[index] == nullptr){
                return false;
            }
            return dfs(node->next[index], word, i+1);
        }
    }

    shared_ptr<Node> root;
};