implement-trie-prefix-tree

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

A <a href="https://en.wikipedia.org/wiki/Trie" target="_blank">trie</a> (pronounced as &quot;try&quot;) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

<ul>
	<li><code>Trie()</code> Initializes the trie object.</li>
	<li><code>void insert(String word)</code> Inserts the string <code>word</code> into the trie.</li>
	<li><code>boolean search(String word)</code> Returns <code>true</code> if the string <code>word</code> is in the trie (i.e., was inserted before), and <code>false</code> otherwise.</li>
	<li><code>boolean startsWith(String prefix)</code> Returns <code>true</code> if there is a previously inserted string <code>word</code> that has the prefix <code>prefix</code>, and <code>false</code> otherwise.</li>
</ul>

&nbsp;
Example 1:

<pre>
Input
[&quot;Trie&quot;, &quot;insert&quot;, &quot;search&quot;, &quot;search&quot;, &quot;startsWith&quot;, &quot;insert&quot;, &quot;search&quot;]
[[], [&quot;apple&quot;], [&quot;apple&quot;], [&quot;app&quot;], [&quot;app&quot;], [&quot;app&quot;], [&quot;app&quot;]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert(&quot;apple&quot;);
trie.search(&quot;apple&quot;); // return True
trie.search(&quot;app&quot;); // return False
trie.startsWith(&quot;app&quot;); // return True
trie.insert(&quot;app&quot;);
trie.search(&quot;app&quot;); // return True
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= word.length, prefix.length &lt;= 2000</code></li>
	<li><code>word</code> and <code>prefix</code> consist only of lowercase English letters.</li>
	<li>At most <code>3 * 104</code> calls in total will be made to <code>insert</code>, <code>search</code>, and <code>startsWith</code>.</li>
</ul>

Implement Trie (Prefix Tree)

Design Add and Search Words Data Structure

design-add-and-search-words-data-structure

添加与搜索单词 - 数据结构设计

Design Search Autocomplete System

design-search-autocomplete-system

设计搜索自动补全系统

Replace Words

replace-words

单词替换

Implement Magic Dictionary

implement-magic-dictionary

实现一个魔法字典

Encrypt and Decrypt Strings

encrypt-and-decrypt-strings

加密解密字符串

Implement Trie II (Prefix Tree)

implement-trie-ii-prefix-tree

实现 Trie （前缀树） II

Count Prefix and Suffix Pairs II

count-prefix-and-suffix-pairs-ii

统计前后缀下标对 II

Count Prefix and Suffix Pairs I

count-prefix-and-suffix-pairs-i

统计前后缀下标对 I

Design

Trie

Hash Table

String

<a href="https://baike.baidu.com/item/字典树/9825209?fr=aladdin" target="_blank">Trie</a>（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你实现 Trie 类：

<ul>
	<li><code>Trie()</code> 初始化前缀树对象。</li>
	<li><code>void insert(String word)</code> 向前缀树中插入字符串 <code>word</code> 。</li>
	<li><code>boolean search(String word)</code> 如果字符串 <code>word</code> 在前缀树中，返回 <code>true</code>（即，在检索之前已经插入）；否则，返回 <code>false</code> 。</li>
	<li><code>boolean startsWith(String prefix)</code> 如果之前已经插入的字符串&nbsp;<code>word</code> 的前缀之一为 <code>prefix</code> ，返回 <code>true</code> ；否则，返回 <code>false</code> 。</li>
</ul>

&nbsp;

示例：

<pre>
输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 True
trie.search("app"); // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app"); // 返回 True
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= word.length, prefix.length &lt;= 2000</code></li>
	<li><code>word</code> 和 <code>prefix</code> 仅由小写英文字母组成</li>
	<li><code>insert</code>、<code>search</code> 和 <code>startsWith</code> 调用次数 总计 不超过 <code>3 * 104</code> 次</li>
</ul>