LeetCode_前缀树_中等_211.添加与搜索单词 - 数据结构设计

旧城等待， 2023-10-12 13:51 49阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

请你设计一个数据结构，支持添加新单词和查找字符串是否与任何先前添加的字符串匹配。实现词典类 WordDictionary ：

*  WordDictionary() 初始化词典对象
 *  void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
 *  bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回 false 。word 中可能包含一些 ‘.’ ，每个 . 都可以表示任何一个字母。

**示例：**

输入：
    ["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
    [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
    输出：
    [null,null,null,null,false,true,true,true]
    解释：
    WordDictionary wordDictionary = new WordDictionary();
    wordDictionary.addWord("bad");
    wordDictionary.addWord("dad");
    wordDictionary.addWord("mad");
    wordDictionary.search("pad"); // 返回 False
    wordDictionary.search("bad"); // 返回 True
    wordDictionary.search(".ad"); // 返回 True
    wordDictionary.search("b.."); // 返回 True

**提示：**  
1 <= word.length <= 25  
addWord 中的 word 由小写英文字母组成  
search 中的 word 由 ‘.’ 或小写英文字母组成  
最多调用 104 次 addWord 和 search

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/design-add-and-search-words-data-structure

## 2.思路 ##

（1）前缀树  
本题是对前缀树的应用，有关前缀树的具体实现可以参考[【数据结构】前缀树/字典树][Link 1]这篇文章。

## 3.代码实现（Java） ##

//思路1————前缀树
    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 c = word.charAt(index);
            if (Character.isLetter(c)) {
        
                //当前字符是字母
                int childrenIndex = c - 'a';
                Trie child = node.getChildren()[childrenIndex];
                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() {
        
            //每个节点最多有 26 个子节点，分别对应 26 个小写英文字母
            children = new Trie[26];
            isEnd = false;
        }
    
        //插入字符串
        public void insert(String word) {
        
            Trie node = this;
            for (int i = 0; i < word.length(); i++) {
        
                int index = word.charAt(i) - '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);
     */

[Link 1]: https://blog.csdn.net/weixin_43004044/article/details/128625633