1032. 字符流

Hard

题目描述

设计一个算法，接受一个字符流，并检查这些字符的后缀是否是给定字符串数组 words 中的字符串。

例如，如果 words = [“abc”, “xyz”] 并且字符流按顺序添加了四个字符 ‘a’、‘x’、‘y’ 和 ‘z’，你的算法应该检测到字符 “axyz” 的后缀 “xyz” 与 words 中的 “xyz” 匹配。

实现 StreamChecker 类：

StreamChecker(String[] words) 用字符串数组 words 初始化对象。
boolean query(char letter) 接受字符流中的一个新字符，如果从流中形成的任何非空后缀在 words 中，则返回 true。

示例 1：

输入
["StreamChecker", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query"]
[[["cd", "f", "kl"]], ["a"], ["b"], ["c"], ["d"], ["e"], ["f"], ["g"], ["h"], ["i"], ["j"], ["k"], ["l"]]
输出
[null, false, false, false, true, false, true, false, false, false, false, false, true]

解释
StreamChecker streamChecker = new StreamChecker(["cd", "f", "kl"]);
streamChecker.query("a"); // 返回 False
streamChecker.query("b"); // 返回 False
streamChecker.query("c"); // 返回 False
streamChecker.query("d"); // 返回 True，因为 'cd' 在 wordlist 中
streamChecker.query("e"); // 返回 False
streamChecker.query("f"); // 返回 True，因为 'f' 在 wordlist 中
streamChecker.query("g"); // 返回 False
streamChecker.query("h"); // 返回 False
streamChecker.query("i"); // 返回 False
streamChecker.query("j"); // 返回 False
streamChecker.query("k"); // 返回 False
streamChecker.query("l"); // 返回 True，因为 'kl' 在 wordlist 中

约束条件：

1 <= words.length <= 2000
1 <= words[i].length <= 200
words[i] 由小写英文字母组成。
letter 是小写英文字母。
最多会对 query 进行 4 * 10^4 次调用。

解题思路

这个问题要求我们检查字符流的后缀是否匹配给定的单词列表。有两种主要的解法思路：

方法一：字典树 + 活跃节点集合（推荐）

核心思想是维护一个"活跃节点"集合，表示当前可能匹配的字典树节点。每次接收新字符时，更新这个集合：

构建字典树：将所有单词插入字典树，标记结束节点
维护活跃节点：保存当前所有可能匹配路径的字典树节点
处理新字符：
- 从根节点开始一个新的匹配尝试
- 更新所有活跃节点，移除无法继续匹配的节点
- 检查是否有节点到达单词结尾

方法二：反向字典树 + 字符流缓存

将单词反向存储在字典树中，维护一个字符缓存，每次查询时反向匹配：

构建反向字典树：将所有单词反向插入字典树
维护字符流：保存接收到的字符（限制最大长度）
反向匹配：从最新字符开始，反向在字典树中查找匹配

方法一在空间和时间上都更优，因为避免了存储完整的字符流，且能够并行处理多个匹配路径。

代码实现

class StreamChecker {
private:
    struct TrieNode {
        unordered_map<char, TrieNode*> children;
        bool isEnd = false;
    };
    
    TrieNode* root;
    vector<TrieNode*> activeNodes;
    
public:
    StreamChecker(vector<string>& words) {
        root = new TrieNode();
        
        // Build trie
        for (const string& word : words) {
            TrieNode* node = root;
            for (char c : word) {
                if (node->children.find(c) == node->children.end()) {
                    node->children[c] = new TrieNode();
                }
                node = node->children[c];
            }
            node->isEnd = true;
        }
    }
    
    bool query(char letter) {
        // Add root to start a new matching attempt
        activeNodes.push_back(root);
        
        vector<TrieNode*> newActiveNodes;
        bool found = false;
        
        // Update all active nodes
        for (TrieNode* node : activeNodes) {
            if (node->children.find(letter) != node->children.end()) {
                TrieNode* nextNode = node->children[letter];
                newActiveNodes.push_back(nextNode);
                if (nextNode->isEnd) {
                    found = true;
                }
            }
        }
        
        activeNodes = newActiveNodes;
        return found;
    }
};

class StreamChecker:
    class TrieNode:
        def __init__(self):
            self.children = {}
            self.is_end = False
    
    def __init__(self, words: List[str]):
        self.root = self.TrieNode()
        self.active_nodes = []
        
        # Build trie
        for word in words:
            node = self.root
            for c in word:
                if c not in node.children:
                    node.children[c] = self.TrieNode()
                node = node.children[c]
            node.is_end = True
    
    def query(self, letter: str) -> bool:
        # Add root to start a new matching attempt
        self.active_nodes.append(self.root)
        
        new_active_nodes = []
        found = False
        
        # Update all active nodes
        for node in self.active_nodes:
            if letter in node.children:
                next_node = node.children[letter]
                new_active_nodes.append(next_node)
                if next_node.is_end:
                    found = True
        
        self.active_nodes = new_active_nodes
        return found

public class StreamChecker {
    private class TrieNode {
        public Dictionary<char, TrieNode> Children = new Dictionary<char, TrieNode>();
        public bool IsEnd = false;
    }
    
    private TrieNode root;
    private List<TrieNode> activeNodes;
    
    public StreamChecker(string[] words) {
        root = new TrieNode();
        activeNodes = new List<TrieNode>();
        
        // Build trie
        foreach (string word in words) {
            TrieNode node = root;
            foreach (char c in word) {
                if (!node.Children.ContainsKey(c)) {
                    node.Children[c] = new TrieNode();
                }
                node = node.Children[c];
            }
            node.IsEnd = true;
        }
    }
    
    public bool Query(char letter) {
        // Add root to start a new matching attempt
        activeNodes.Add(root);
        
        List<TrieNode> newActiveNodes = new List<TrieNode>();
        bool found = false;
        
        // Update all active nodes
        foreach (TrieNode node in activeNodes) {
            if (node.Children.ContainsKey(letter)) {
                TrieNode nextNode = node.Children[letter];
                newActiveNodes.Add(nextNode);
                if (nextNode.IsEnd) {
                    found = true;
                }
            }
        }
        
        activeNodes = newActiveNodes;
        return found;
    }
}

var StreamChecker = function(words) {
    this.root = { children: {}, isEnd: false };
    this.activeNodes = [];
    
    // Build trie
    for (let word of words) {
        let node = this.root;
        for (let c of word) {
            if (!(c in node.children)) {
                node.children[c] = { children: {}, isEnd: false };
            }
            node = node.children[c];
        }
        node.isEnd = true;
    }
};

StreamChecker.prototype.query = function(letter) {
    // Add root to start a new matching attempt
    this.activeNodes.push(this.root);
    
    let newActiveNodes = [];
    let found = false;
    
    // Update all active nodes
    for (let node of this.activeNodes) {
        if (letter in node.children) {
            let nextNode = node.children[letter];
            newActiveNodes.push(nextNode);
            if (nextNode.isEnd) {
                found = true;
            }
        }
    }
    
    this.activeNodes = newActiveNodes;
    return found;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

操作	时间复杂度	空间复杂度
构造函数	O(N×L)	O(N×L)
query	O(W)	O(W)

其中：

N 是单词数量
L 是单词的平均长度
W 是当前活跃节点的数量（最坏情况下等于所有单词的总长度）

说明：

构造函数需要将所有单词插入字典树
每次 query 操作的时间复杂度取决于当前活跃节点的数量
空间复杂度主要由字典树结构和活跃节点列表决定

题目描述#

解题思路#

方法一：字典树 + 活跃节点集合（推荐）#

方法二：反向字典树 + 字符流缓存#

代码实现#

复杂度分析#