lc1032-字符流

题目描述

• 设计一个算法：接收一个字符流，并检查每个新字符加进来形成的新串，其后缀是否是字符串数组 words 中的一个字符串

示例

输入：
["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 中

题解

• 思路：字典树

type StreamChecker struct {root *TrieNodestr  []byte
}type TrieNode struct {son   [26]*TrieNodeisEnd bool
}func Constructor(words []string) StreamChecker {root := &TrieNode{}for _, w := range words {root.insert(w)}return StreamChecker{root: root,str: []byte{},}
}func (t *TrieNode)insert(w string) {for i := len(w) - 1; i >= 0; i -- {idx := w[i] - 'a'if t.son[idx] == nil {t.son[idx] = &TrieNode{}}t = t.son[idx]}t.isEnd = true
}func (this *StreamChecker) Query(letter byte) bool {this.str = append(this.str, letter)node := this.rootfor i := len(this.str) - 1; i >= 0; i -- {idx := this.str[i] - 'a'if node.son[idx] == nil { return false }node = node.son[idx]if node.isEnd { return true }}return false
}