<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                # 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(<span class="hljs-string">"a"</span>); <span class="hljs-title">// stream: a</span> streamChecker.query(<span class="hljs-string">"b"</span>); <span class="hljs-title">// stream:ba</span> streamChecker.query(<span class="hljs-string">"c"</span>); <span class="hljs-title">// stream:cba</span> ``` ``` 這里有兩個小的點需要注意: 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">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">StreamChecker</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span><span class="hljs-params">(self, words: List[str])</span>:</span> self.trie = Trie() self.stream = deque([]) <span class="hljs-keyword">for</span> word <span class="hljs-keyword">in</span> set(words): self.trie.insert(word[::<span class="hljs-params">-1</span>]) <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">query</span><span class="hljs-params">(self, letter: str)</span> -> bool:</span> self.stream.appendleft(letter) <span class="hljs-keyword">return</span> self.trie.search(self.stream) ``` ``` ## 關鍵點解析 - 前綴樹模板 - 倒序插入 ## 代碼 - 語言支持: Python Python Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Trie</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span><span class="hljs-params">(self)</span>:</span> <span class="hljs-string">""" Initialize your data structure here. """</span> self.Trie = {} <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">insert</span><span class="hljs-params">(self, word)</span>:</span> <span class="hljs-string">""" Inserts a word into the trie. :type word: str :rtype: void """</span> curr = self.Trie <span class="hljs-keyword">for</span> w <span class="hljs-keyword">in</span> word: <span class="hljs-keyword">if</span> w <span class="hljs-keyword">not</span> <span class="hljs-keyword">in</span> curr: curr[w] = {} curr = curr[w] curr[<span class="hljs-string">'#'</span>] = <span class="hljs-params">1</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">search</span><span class="hljs-params">(self, word)</span>:</span> <span class="hljs-string">""" Returns if the word is in the trie. :type word: str :rtype: bool """</span> curr = self.Trie <span class="hljs-keyword">for</span> w <span class="hljs-keyword">in</span> word: <span class="hljs-keyword">if</span> w <span class="hljs-keyword">not</span> <span class="hljs-keyword">in</span> curr: <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span> <span class="hljs-keyword">if</span> <span class="hljs-string">"#"</span> <span class="hljs-keyword">in</span> curr[w]: <span class="hljs-keyword">return</span> <span class="hljs-keyword">True</span> curr = curr[w] <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">StreamChecker</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span><span class="hljs-params">(self, words: List[str])</span>:</span> self.trie = Trie() self.stream = deque([]) <span class="hljs-keyword">for</span> word <span class="hljs-keyword">in</span> set(words): self.trie.insert(word[::<span class="hljs-params">-1</span>]) <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">query</span><span class="hljs-params">(self, letter: str)</span> -> bool:</span> self.stream.appendleft(letter) <span class="hljs-keyword">return</span> 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)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看