【LeetCode 211】添加与搜索单词 - 数据结构设计

Table of Contents

链接：https://leetcode.cn/problems/design-add-and-search-words-data-structure/description/

思路
#

根据题意，$\texttt{WordDictionary}$ 类需要支持添加单词和搜索单词的操作，可以使用字典树实现。

对于添加单词，将单词添加到字典树中即可。

对于搜索单词，从字典树的根结点开始搜索。由于待搜索的单词可能包含点号，因此在搜索过程中需要考虑点号的处理。对于当前字符是字母和点号的情况，分别按照如下方式处理：

如果当前字符是字母，则判断当前字符对应的子结点是否存在，如果子结点存在则移动到子结点，继续搜索下一个字符，如果子结点不存在则说明单词不存在，返回 $\text{false}$；

如果当前字符是点号，由于点号可以表示任何字母，因此需要对当前结点的所有非空子结点继续搜索下一个字符。

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

如果搜索完给定的单词的最后一个字符，则当搜索到的最后一个结点的 $\textit{isEnd}$ 为 $\text{true}$ 时，给定的单词存在。

特别地，当搜索到点号时，只要存在一个非空子结点可以搜索到给定的单词，即返回 $\text{true}$。

代码
#

class WordDictionary {

    private Trie root;

    public WordDictionary() {
        root = new Trie();
    }
    
    public void addWord(String word) {
        root.insert(word);
    }
    
    public boolean search(String word) {
        return dfs(word, 0, root);
    }

    private boolean dfs(String word, int index, Trie node) {
        if(index == word.length()) {
            return node.isEnd();
        }
        char ch = word.charAt(index);
        if(Character.isLetter(ch)) {
            int childIndex = ch - 'a';
            Trie child = node.getChildren()[childIndex];
            if(child != null && dfs(word, index + 1, child)) {
                return true;
            }
        } else {
            for(int i = 0; i < 26; i++) {
                Trie child = node.getChildren()[i];
                if(child != null && dfs(word, index + 1, child)) {
                    return true;
                }
            }
        }
        return false;
    }
}

class Trie {
    private Trie[] children;
    private boolean isEnd;

    public Trie() {
        children = new Trie[26];
        isEnd = false;
    }
    
    public void insert(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }

    public Trie[] getChildren() {
        return children;
    }

    public boolean isEnd() {
        return isEnd;
    }
}

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

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

思路 #

代码 #

思路
#

代码
#