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

Author: Carissa 🎀

Date: Dec.26 2023 🎄

Link: 211. 添加与搜索单词 - 数据结构设计 - 力扣（LeetCode）

1 题目

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

实现词典类 WordDictionary ：

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

提示：

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

示例 1：

输入：[“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

2 思路

本题考点非常明确，即前缀树，但是我们应当注意到，这里在搜索时由于 ‘.’ 可以对应任意单词，还涉及到树的回溯搜索

==- 前缀树==

==- 回溯==

2.1 前缀树（Trie）

非常经典必须掌握的数据结构写法，在这里做简单回顾。

一个 TrieNode 结构应当包含以下部分：
- 字段：
  - val: 当前节点的值
  - childern: 记录当前节点的子节点
  - isEnd: 记录当前节点是否是某个单词的结尾
- 方法（除了构造方法）：
  - insert(): 插入单词
  - search(): 搜索单词
  - 本题由于search方法有进一步回溯，可以放到题目的特定方法中去定义
尤其需要注意的是 children 的实现，一开始采用的是 Map 结构，导致代码异常复杂，对于字典树来说，只需要记录26个字母的情况，采用 Node[26] 记录即可。

2.2 回溯

从根节点开始搜索，当返回 false 或单词的所有字符已全部搜索完成，则返回。
对于每一个字符来说：
- 如果当前字符是字母，则判断当前字符是否能匹配本层节点，如果能则匹配下个字符，否则返回 false
- 如果当前字符是 . , 则遍历所有的非空子节点
需要注意的是：
- 判断字符 Character.isLetter() 可以使用

回溯部分代码如下

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

3 复杂度分析

时间复杂度：

初始化： O(1)

插入：O(∣S∣)

搜索：O(∣Σ∣∣S∣)

∣S∣ 是每次添加或搜索的单词的长度，Σ 是字符集，本题 ∣Σ∣=26。最坏情况下，待搜索的单词中的每个字符都是点号，则每个字符都有 ∣Σ∣种可能。

空间复杂度：O(∣Σ∣∣T∣)

∣T∣是所有添加的单词的长度之和

4 完整解法

class WordDictionary {
    class TreeNode {
        private TreeNode[] childern;
        private boolean isLeaf;

        public TreeNode () {
            isLeaf = false;
            childern = new TreeNode[26];
        }

        public void insert(String s) {
            TreeNode node = this;
            for(int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                int index = c - 'a';
                if(node.childern[index] == null) {
                    node.childern[index] = new TreeNode();
                }
                node = node.childern[index];
            }
            node.isLeaf = true;
        }
    }
    private TreeNode root;
    public WordDictionary() {
        root = new TreeNode();
    }
    
    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, TreeNode node) {
        if(index == word.length()) return node.isLeaf;
        char ch = word.charAt(index);
        if(Character.isLetter(ch)) {
            int chindex = ch - 'a';
            if(node.childern[chindex] != null && dfs(word, index+1, node.childern[chindex])) return true;
        } else {
            for(int i = 0; i < 26; i++) {
                TreeNode child = node.childern[i];
                if(child != null && dfs(word, index + 1, child)) return true;
            }
        }
        return false;
    }
}