字符流
难度:
标签:
题目描述
代码结果
运行时间: 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`方法中,为什么需要从最新的字符开始反向在字典树中查找?
▷🦆
字典树中的`is_word`属性是如何确保我们检测到的是完整单词而不是单词的一部分?
▷🦆
在`query`方法中,如果当前后缀匹配失败,是如何处理剩余的字符流的?是否还需要继续查找?
▷