当前位置：首页 > article >正文

LeetCode题练习与总结：添加与搜索单词 - 数据结构设计--211

article 2024/11/16 12:26:43

一、题目描述

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

实现词典类 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 由 '.' 或小写英文字母组成
最多调用 10^4 次 addWord 和 search

二、解题思路

这个问题可以通过使用Trie（前缀树）数据结构来解决。Trie是一种用于检索字符串数据集中的键的有序树数据结构。它的优点是可以以O(m)的时间复杂度（其中m是字符串的长度）搜索字符串，并且可以高效地处理前缀匹配问题。

解题思路如下：

使用Trie数据结构来存储添加的单词。
addWord方法：遍历单词的每个字符，如果当前字符不在子节点中，则创建一个新的Trie节点，然后递归添加下一个字符。
search方法：由于word中可能包含.，这表示任意字符，所以我们需要递归地检查所有可能的路径。如果遇到.，则对当前节点的所有非空子节点进行递归搜索。

三、具体代码

class WordDictionary {
    private TrieNode root;

    public WordDictionary() {
        root = new TrieNode();
    }
    
    public void addWord(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            if (!node.containsKey(c)) {
                node.put(c, new TrieNode());
            }
            node = node.get(c);
        }
        node.setEnd();
    }
    
    public boolean search(String word) {
        return searchInNode(word, root);
    }

    private boolean searchInNode(String word, TrieNode node) {
        for (int i = 0; i < word.length(); i++) {
            char currentChar = word.charAt(i);
            if (currentChar == '.') {
                for (char c : node.keySet()) {
                    TrieNode nextNode = node.get(c);
                    if (searchInNode(word.substring(i + 1), nextNode)) {
                        return true;
                    }
                }
                return false;
            } else {
                if (!node.containsKey(currentChar)) {
                    return false;
                }
                node = node.get(currentChar);
            }
        }
        return node.isEnd();
    }
}

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

    public TrieNode() {
        children = new TrieNode[26];
        isEnd = false;
    }

    public boolean containsKey(char c) {
        return children[c - 'a'] != null;
    }

    public TrieNode get(char c) {
        return children[c - 'a'];
    }

    public void put(char c, TrieNode node) {
        children[c - 'a'] = node;
    }

    public void setEnd() {
        isEnd = true;
    }

    public boolean isEnd() {
        return isEnd;
    }

    public Set<Character> keySet() {
        Set<Character> keySet = new HashSet<>();
        for (int i = 0; i < 26; i++) {
            if (children[i] != null) {
                keySet.add((char) (i + 'a'));
            }
        }
        return keySet;
    }
}

在上述代码中，TrieNode类代表Trie的节点，它包含一个长度为26的数组children，用于存储子节点，以及一个布尔值isEnd，用于标记是否是单词的结尾。WordDictionary类实现了添加单词和搜索单词的方法。搜索方法searchInNode是递归的，以处理包含.的搜索模式。

四、时间复杂度和空间复杂度

1. 时间复杂度

(1) addWord 方法

addWord方法遍历了单词中的每个字符。
对于每个字符，它执行常数时间的操作（检查是否包含键、获取节点、添加节点）。

因此，addWord方法的时间复杂度是O(m)，其中m是单词的长度。

(2) search 方法

search方法也遍历了搜索字符串中的每个字符。
如果当前字符不是.，则它执行常数时间的操作。
如果当前字符是.，则需要遍历当前节点的所有子节点，并对每个子节点进行递归搜索。

最坏情况下，每个节点都有26个子节点，并且对于每个.，都需要对每个子节点进行递归调用。这意味着在最坏情况下，时间复杂度是O(26^n)，其中n是字符串的长度。

2. 空间复杂度

(1) TrieNode 类

TrieNode类有一个长度为26的数组，存储子节点。
每个节点只存储其子节点的引用，而不存储实际的字符。

因此，TrieNode类本身的空间复杂度是O(1)，因为不管输入如何，它都只占用固定大小的空间。

(2) WordDictionary 类

WordDictionary类有一个根节点root，所有的单词都存储在这个根节点下。
对于每个添加的单词，可能需要添加新的节点。

在最坏情况下，如果所有的单词都是不同的，那么每个单词的每个字符都会创建一个新的节点。假设有n个单词，每个单词最长为m，那么最坏情况下的空间复杂度是O(n * m)。

3. 总结

addWord方法的时间复杂度是O(m)，空间复杂度是O(1)（对于单个单词）。
search方法的时间复杂度在最坏情况下是O(26^n)，空间复杂度是O(n)，这是递归调用栈的深度。

这里的n是搜索字符串的长度，m是添加的单词的长度，n和m通常是不同的。在最坏情况下，n和m可以相等。

五、总结知识点

类的定义与实例化：定义了两个类WordDictionary和TrieNode，WordDictionary类包含一个TrieNode类型的成员变量root，并在构造方法中初始化它。
成员方法：addWord和search是WordDictionary类的公共方法，用于添加单词和搜索单词。searchInNode是私有辅助方法，用于递归搜索Trie树。
字符数组遍历：addWord方法中使用word.toCharArray()将字符串转换为字符数组，并使用增强型for循环遍历数组。
Trie数据结构：TrieNode类代表Trie树的节点，包含一个长度为26的TrieNode数组children和一个布尔值isEnd。数组索引对应字母表的字母，布尔值标记单词结束。
字符与索引转换：在TrieNode类中，通过c - 'a'将字符转换为数组索引。
递归算法：searchInNode方法是一个递归方法，用于在Trie树中搜索包含.的字符串。
条件逻辑：if-else语句用于处理.字符，表示任意字符的匹配，以及字符是否存在于当前Trie节点中。
集合的使用：keySet方法返回一个包含所有有效子键的HashSet集合，用于在递归搜索时遍历所有可能的子节点。
字符串子串：在处理.字符时，使用word.substring(i + 1)获取子字符串，以便在递归调用中继续搜索。
成员变量的封装：TrieNode类的成员变量children和isEnd被声明为私有，通过公共方法访问和修改，符合封装原则。