1032. 字符流 · ttttt

# 1032. 字符流 ## 題目地址(1032. 字符流) <https://leetcode-cn.com/problems/stream-of-characters/> ## 題目描述 ``` <pre class="calibre18">``` 按下述要求實現 StreamChecker 類： StreamChecker(words)：構造函數，用給定的字詞初始化數據結構。 query(letter)：如果存在某些 k >= 1，可以用查詢的最后 k個字符（按從舊到新順序，包括剛剛查詢的字母）拼寫出給定字詞表中的某一字詞時，返回 true。否則，返回 false。示例： StreamChecker streamChecker = new StreamChecker(["cd","f","kl"]); // 初始化字典 streamChecker.query('a'); // 返回 false streamChecker.query('b'); // 返回 false streamChecker.query('c'); // 返回 false streamChecker.query('d'); // 返回 true，因為 'cd' 在字詞表中 streamChecker.query('e'); // 返回 false streamChecker.query('f'); // 返回 true，因為 'f' 在字詞表中 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' 在字詞表中。提示： 1 <= words.length <= 2000 1 <= words[i].length <= 2000 字詞只包含小寫英文字母。待查項只包含小寫英文字母。待查項最多 40000 個。 ``` ``` ## 前置知識 - 前綴樹 ## 公司 - 字節 ## 思路題目要求`按從舊到新順序`查詢，因此可以將從舊到新的 query 存起來形成一個單詞 stream。比如： ``` <pre class="calibre18">``` streamChecker.query("a"); // stream： a streamChecker.query("b"); // stream：ba streamChecker.query("c"); // stream：cba ``` ``` 這里有兩個小的點需要注意： 1. 如果用數組來存儲，由于每次都往數組頭部插入一個元素，因此每次 query 操作的時間復雜度為 O(N)O(N)O(N)，其中 NNN 為截止當前執行 query 的次數，我們可以使用雙端隊列進行優化。 2. 由于不必 query 形成的查詢全部命中。比如 stream 為 cba 的時候，找到單詞 c， bc， abc 都是可以的。如果是找到 c，cb，cba 比較好吧，現在是反的。其實我們可以反序插入是，類似的技巧在[211.add-and-search-word-data-structure-design](https://github.com/azl397985856/leetcode/blob/b8e8fa5f0554926efa9039495b25ed7fc158372a/problems/211.add-and-search-word-data-structure-design.md) 也有用到。之后我們用拼接的單詞在 words 中查詢即可，最簡單的方式當然是每次 query 都去掃描一次，這種方式毫無疑問會超時。我們可以采用構建 Trie 的形式，即已空間環時間，其代碼和常規的 Trie 類似，只需要將 search(word) 函數做一個簡單修改即可，我們不需要檢查整個 word 是否存在，而已 word 的前綴存在即可。 > 提示：可以通過對 words 去重，來用空間換區時間。具體算法： - init 中構建 Trie 和雙端隊列 stream - query 時，往 stream 的左邊 append 即可。 - 調用 Trie 的 search（和常規的 search 稍有不同，我上面已經講了）核心代碼（Python）： ``` <pre class="calibre18">``` class StreamChecker: def __init__(self, words: List[str]): self.trie = Trie() self.stream = deque([]) for word in set(words): self.trie.insert(word[::-1]) def query(self, letter: str) -> bool: self.stream.appendleft(letter) return self.trie.search(self.stream) ``` ``` ## 關鍵點解析 - 前綴樹模板 - 倒序插入 ## 代碼 - 語言支持: Python Python Code: ``` <pre class="calibre18">``` class Trie: def __init__(self): """ Initialize your data structure here. """ self.Trie = {} def insert(self, word): """ Inserts a word into the trie. :type word: str :rtype: void """ curr = self.Trie for w in word: if w not in curr: curr[w] = {} curr = curr[w] curr['#'] = 1 def search(self, word): """ Returns if the word is in the trie. :type word: str :rtype: bool """ curr = self.Trie for w in word: if w not in curr: return False if "#" in curr[w]: return True curr = curr[w] return False class StreamChecker: def __init__(self, words: List[str]): self.trie = Trie() self.stream = deque([]) for word in set(words): self.trie.insert(word[::-1]) def query(self, letter: str) -> bool: self.stream.appendleft(letter) return self.trie.search(self.stream) ``` ``` ## 相關題目 - [0208.implement-trie-prefix-tree](https://github.com/azl397985856/leetcode/blob/b8e8fa5f0554926efa9039495b25ed7fc158372a/problems/208.implement-trie-prefix-tree.md) - [0211.add-and-search-word-data-structure-design](https://github.com/azl397985856/leetcode/blob/b0b69f8f11dace3a9040b54532105d42e88e6599/problems/211.add-and-search-word-data-structure-design.md) - [0212.word-search-ii](https://github.com/azl397985856/leetcode/blob/b0b69f8f11dace3a9040b54532105d42e88e6599/problems/212.word-search-ii.md) - [0472.concatenated-words](https://github.com/azl397985856/leetcode/blob/master/problems/472.concatenated-words.md) - [0820.short-encoding-of-words](https://github.com/azl397985856/leetcode/blob/master/problems/820.short-encoding-of-words.md)