1032：字符流（1970 分）

2019-04-21 约 735 字预计阅读 2 分钟次阅读

力扣第 133 场周赛第 4 题

题目

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

例如，words = ["abc", "xyz"] 且字符流中逐个依次加入 4 个字符 'a'、'x'、'y' 和 'z' ，你所设计的算法应当可以检测到 "axyz" 的后缀 "xyz" 与 words 中的字符串 "xyz" 匹配。

按下述要求实现 StreamChecker 类：

StreamChecker(String[] words) ：构造函数，用字符串数组 words 初始化数据结构。
boolean query(char letter)：从字符流中接收一个新字符，如果字符流中的任一非空后缀能匹配 words 中的某一字符串，返回 true ；否则，返回 false。

示例：

输入：
["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"); // 返回n False
streamChecker.query("d"); // 返回 True ，因为 'cd' 在 words 中
streamChecker.query("e"); // 返回 False
streamChecker.query("f"); // 返回 True ，因为 'f' 在 words 中
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' 在 words 中

提示：

1 <= words.length <= 2000
1 <= words[i].length <= 200
words[i] 由小写英文字母组成
letter 是一个小写英文字母
最多调用查询 4 * 10⁴ 次

分析

#1

由于单词长度最多 200，所以每次调用时可以直接遍历检查
可以将所有单词反向插入字典树，节省遍历检查的时间

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class StreamChecker:

    def __init__(self, words: List[str]):
        T = lambda: defaultdict(T)
        self.trie = T()
        for w in words:
            p = self.trie
            for c in w[::-1]:
                p = p[c]
            p['#'] = ''
        self.Q = deque()

    def query(self, letter: str) -> bool:
        p,Q = self.trie,self.Q
        Q.appendleft(letter)
        for c in Q:
            if c not in p:
                return False
            p = p[c]
            if '#' in p:
                return True
        return False

149 ms

#2

更通用的方法是 AC 自动机，专门匹配输入流的最大后缀

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47


class Node:
    __slots__ = 'son', 'fail', 'end'
    
    def __init__(self):
        self.son = [None]*26
        self.fail = None
        self.end = False

class AC:
    def __init__(self):
        self.root,dum = Node(),Node()
        dum.son = [self.root]*26
        self.root.fail = dum

    def add(self,s):
        p = self.root
        for c in s:
            c = ord(c)-ord('a')
            if not p.son[c]:
                p.son[c] = Node()
            p = p.son[c]
        p.end = True

    def build(self):
        Q = deque([self.root])
        while Q:
            u = Q.popleft()
            u.end |= u.fail.end
            for c in range(26):
                if u.son[c]:
                    u.son[c].fail = u.fail.son[c]
                    Q.append(u.son[c])
                else:
                    u.son[c] = u.fail.son[c]

class StreamChecker:

    def __init__(self, words: List[str]):
        ac = AC()
        for w in words:
            ac.add(w)
        ac.build()
        self.p = ac.root
        
    def query(self, letter: str) -> bool:
        self.p = self.p.son[ord(letter)-ord('a')]
        return self.p.end

134 ms

目录

1032：字符流（1970 分）

题目

分析

#1

#2

解答