【面试经典 150 | 字典树】添加与搜索单词

【面试经典 150 | 字典树】添加与搜索单词 - 数据结构设计

文章目录

写在前面
Tag
题目来源
解题思路
- 方法一：字典树
写在最后

写在前面

本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……

专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：

Tag：介绍本题牵涉到的知识点、数据结构；
题目来源：贴上题目的链接，方便大家查找题目并完成练习；
题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；
解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；
知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【字典树/前缀树】【数据结构设计】

题目来源

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

解题思路

方法一：字典树

前缀树也叫字典树，是一种树形数据结构，用于高效地存储和检索字符串数据集中的键，方便查找某个字符是否存在或者查找某个前缀是否存在。

在解决本题之前，首先需要对字典树有所了解，需要先完成 208. 实现 Trie (前缀树)。

思路

wordDictionary 类中的增加单词功能可以直接通过调用字典数组中的插入功能来实现。

对于搜索单词，需要从字典树的根节点开始搜索。由于搜索的单词中可能含有点号，点号可以当做任意字符。对于当前搜索到的字符是字母和点号的情况，需要分别处理：

如果当前字符是字母，则判断当前字符对应的子结点是否存在，如果子结点存在则移动到子结点，继续搜索下一个字符，如果子结点不存在则说明单词不存在，返回 false；
如果当前字符是点号，由于点号可以表示任何字母，因此需要对当前结点的所有非空子结点继续搜索下一个字符。

重复上述步骤，直到返回 false\text{false}false 或搜索完给定单词的最后一个字符。

如果搜索完给定的单词的最后一个字符，则当搜索到的最后一个结点的 isEnd = true 时，给定的单词存在。

代码

class Trie {
public:
    bool isEnd;
    vector<Trie*> children;
    Trie(): isEnd(false) {
        children = vector<Trie*>(26, nullptr);
    };

    void insert(Trie* curr, string word) {
        Trie* now = curr;
        for(int i = 0; i < word.size(); ++i) {
            int child = word[i] - 'a';
            if(now->children[child] == nullptr){
                now->children[child] = new Trie();
            }
            now = now->children[child];
        }
        now->isEnd = true;
    }
};

class WordDictionary {
private:
    Trie* trie;

public:
    WordDictionary(): trie(new Trie()) {}
    
    void addWord(string word) {
        trie->insert(trie, word);
    }
    
    bool search(string word) {
        return dfs(trie, word, 0);
    }

    bool dfs(Trie* now, string& word, int idx){
        if(idx == word.size()){
            return now->isEnd;
        }
        
        int i = idx, j;
        int n = word.size();
            if(word[i] >= 'a' && word[i] <= 'z'){
                Trie* child = now->children[word[i] - 'a'];
                if(child && dfs(child, word, idx+1)){
                    return true;
                }
            }
            else if(word[i] == '.'){
                for(j = 0; j < 26; ++j){
                    Trie* child = now->children[j];
                    if(child && dfs(child, word, idx+1)){
                        return true;
                    }
                }
            }
        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);
 */

复杂度分析

时间复杂度：初始化为 $O (1)$ ，添加单词为 $O (∣ S ∣)$ ，搜索单词为 $O(|\Sigma|^{|S|})$ ，其中 $∣ S ∣$ 是每次添加或搜索的单词的长度， $\Sigma$ 是字符集，这道题中的字符集为全部小写英语字母， $|\Sigma| = 26$ 。最坏情况下，待搜索的单词中的每个字符都是点号，则每个字符都有 $|\Sigma|$ 种可能。