Categorygithub.com/szhou12/leetcode-goleetcode1032-Stream-of-Characters
package
0.0.0-20241220224003-b7cf03a90b2b
Repository: https://github.com/szhou12/leetcode-go.git
Documentation: pkg.go.dev
Overview
Dependencies
0
Dependents
0

# README

1032. Stream of Characters

Solution idea

Trie

思路总结

  1. 理解题意: 每次query，要把当前的 字符 添加在之前所有query组成的字符流的末尾
  2. 一开始的想法: 建Trie时每个dictionary word按照顺序插入。查询时，遍历所有以当前 query带来的字符为结尾的所有子串，挨个检查一遍。但是这样做会超时，因为 Time Complexity = $O(1 + 2 + 3 + \cdots + Q) = O(Q^2)$ where $Q$ is the number of queries.
// e.g. stream queries: a -> b -> c -> d
a b c d
      -
    ---
  -----
-------
  1. 优化解法:
    • 题目要求查询 suffix: 暗示 建Trie时每个dictionary word应该按照逆序插入。
    • query带来的字符流 也按照 逆序组成 字符串: 当前query带来的字符放在头部。d c b a
    • 爬 Trie 时，走到一个节点的 isEnd == true 就算找到了。
    • 这样做只用走一遍Queries。Time Complexity = $O(Q)$ where $Q$ is the number of queries.

Time complexity = $O(mN) + O(Q)$ (build Trie + query) where $m = $ # of dictionary words, $N = $ worst-case length of a dictionary word, $Q = $ # of queries.

Resource