leetcode
leetcode 951 ~ 1000
字符流

字符流

难度:

标签:

题目描述

代码结果

运行时间: 298 ms, 内存: 46.4 MB


/*
 * 思路:我们需要设计一个 StreamChecker 类,它会逐个接收字符,并检查字符流的后缀是否在给定的字符串数组 words 中。
 * 使用 Java Stream API 进行字符串检查。
 */

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class StreamChecker {
    private StringBuilder stream;
    private Set<String> wordsSet;

    public StreamChecker(String[] words) {
        stream = new StringBuilder();
        wordsSet = new HashSet<>(Arrays.asList(words));
    }

    public boolean query(char letter) {
        stream.append(letter);
        String currentStream = stream.toString();
        return wordsSet.stream().anyMatch(currentStream::endsWith);
    }
}

解释

方法:

该题解采用字典树(Trie)数据结构,通过反转每个单词并将其插入到字典树中来处理字符流中的后缀匹配。每当接收到新的字符,它会被添加到一个字符流数组中,然后从最新的字符开始向前检查,使用字典树判断当前字符流的后缀是否为字典树中某个单词的前缀。如果在字典树中找到了对应的单词,那么返回true,否则继续检查。

时间复杂度:

O(n*m) ,其中 n 是查询次数,m 是最长单词的长度

空间复杂度:

O(T) ,其中 T 是所有单词的总字符数

代码细节讲解

🦆
为什么选择将每个单词反转后插入字典树来匹配字符流的后缀,直接插入不行吗?
将每个单词反转后插入字典树是为了便于处理字符流中的后缀匹配。在字符流问题中,我们通常需要检查流的任何后缀是否能与字典中的单词匹配。如果单词未经反转直接插入字典树,我们需要从字典树的根节点开始,根据字符流的整个历史来匹配,这会变得复杂且低效,特别是当字符流非常长时。反转单词并存储在字典树中,使得我们可以仅通过查看流中的最后几个字符(即最新的字符)就能高效地进行匹配。这是因为反转后,字典树的路径与字符流的后缀直接对应。
🦆
在`query`方法中,为什么需要从最新的字符开始反向在字典树中查找?
在`query`方法中,从最新的字符开始反向查找是因为我们存储的单词是反转后的形式。当新字符加入到流中时,我们需要检查这个字符以及它之前的字符序列是否能够形成字典树中某个单词的前缀。由于字典树中存储的是反转的单词,所以我们需要从字符流的最新字符(即最后一个字符)开始,逆序检查这些字符是否能形成字典树中的路径。这样可以迅速定位到最新加入的字符可能形成的单词,提高匹配效率。
🦆
字典树中的`is_word`属性是如何确保我们检测到的是完整单词而不是单词的一部分?
在字典树中的`is_word`属性标记了某个节点是否为单词的结束。当在字典树中插入单词时,单词的最后一个字符对应的节点会将`is_word`设置为`True`。这意味着,如果在查询字符流时,我们到达了一个标记为`is_word`的节点,这表明我们从最新的字符开始到当前节点形成的字符串序列,正好是字典树中存储的某个完整单词。因此,`is_word`属性确保我们不仅匹配到了单词的一部分,而是匹配到了一个完整的单词。
🦆
在`query`方法中,如果当前后缀匹配失败,是如何处理剩余的字符流的?是否还需要继续查找?
在`query`方法中,如果当前后缀匹配失败,即在字典树中找不到继续深入的路径,那么就不需要继续查找剩余的字符流了。这是因为,一旦某个字符没有在当前节点的孩子中找到对应的路径,这表明从这个字符开始的任何后续字符组合都不会形成有效的单词前缀。因此,函数会返回`False`,表示当前字符流的后缀与字典树中的任何单词都不匹配。此时,无需继续检查更早的字符,因为它们也不可能形成有效的匹配。

相关问题