## Algorithm

Problem Name: 208. Implement Trie (Prefix Tree)

A trie (pronounced as "try") 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:

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

Example 1:

```Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True
```

Constraints:

• `1 <= word.length, prefix.length <= 2000`
• `word` and `prefix` consist only of lowercase English letters.
• At most `3 * 104` calls in total will be made to `insert`, `search`, and `startsWith`.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
typedef struct {
int leaf;
void *child[26];
} Trie;
​
/** Initialize your data structure here. */
Trie* trieCreate() {
Trie *root = calloc(1, sizeof(Trie));
//assert(root);
return root;
}
​
/** Inserts a word into the trie. */
void trieInsert(Trie* obj, char* word) {
Trie *node;
while (*word) {
node = obj->child[*word - 'a'];
if (!node) {
node = calloc(1, sizeof(Trie));
//assert(node);
obj->child[*word - 'a'] = node;
}
obj = node;
word ++;
}
obj->leaf = 1;
}
​
/** Returns if the word is in the trie. */
bool trieSearch(Trie* obj, char* word) {
Trie *node = obj;
while (*word) {
node = node->child[*word - 'a'];
if (!node) return false;
word ++;
}
return node->leaf ? true : false;
}
​
/** Returns if there is any word in the trie that starts with the given prefix. */
bool trieStartsWith(Trie* obj, char* prefix) {
Trie *node = obj;
while (*prefix) {
node = node->child[*prefix - 'a'];
if (!node) return false;
prefix ++;
}
return true;
}
​
void trieFree(Trie* obj) {
Trie *node;
int i;
for (i = 0; i  <  26; i ++) {
node = obj->child[i];
if (node) trieFree(node);
}
free(obj);
}
``````
Copy The Code &

Input

cmd
["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

Output

cmd
[null, null, true, false, true, null, true]

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Trie {
private:
unordered_sets;
public:
Trie() {}

void insert(string word) {
s.insert(word);
}

bool search(string word) {
return s.count(word);
}

bool startsWith(string prefix) {
for(auto x: s){
if(x.size() < prefix.size()) continue;
int i = 0;
while(i  <  prefix.size() && x[i] == prefix[i]) i++;
if(i == prefix.size()> return true;
}
return false;
}
};
``````
Copy The Code &

Input

cmd
["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

Output

cmd
[null, null, true, false, true, null, true]

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Trie {

private TrieNode root;

public Trie() {
this.root = new TrieNode();
}

public void insert(String word) {
TrieNode curr = root;
for (char c : word.toCharArray()) {
if (!curr.children.containsKey(c)) {
curr.children.put(c, new TrieNode());
}
curr = curr.children.get(c);
}
curr.isWord = true;
}

public boolean search(String word) {
TrieNode searchNode = searchHelper(word);
return searchNode != null && searchNode.isWord;
}

public boolean startsWith(String prefix) {
return searchHelper(prefix) != null;
}

private TrieNode searchHelper(String s) {
TrieNode curr = root;
for (char c : s.toCharArray()) {
if (!curr.children.containsKey(c)) {
return null;
}
curr = curr.children.get(c);
}
return curr;
}

private class TrieNode {
Map < Character, TrieNode> children;
boolean isWord;

public TrieNode() {
this.children = new HashMap < >();
}
}
}
``````
Copy The Code &

Input

cmd
["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

Output

cmd
[null, null, true, false, true, null, true]

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````s
class Trie {
constructor() {
this.isWord = false;
}
insert(word) {
let node = this;
for (const c of word) {
}
node.isWord = true;
}
search(word) {
const node = this.traverse(word);
return node ? node.isWord : false;
}
startsWith(prefix) {
const node = this.traverse(prefix);
return node !== null;
}
traverse(word) {
let node = this;
for (const c of word) {
else return null;
}
return node;
}
}
``````
Copy The Code &

Input

cmd
["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

Output

cmd
[null, null, true, false, true, null, true]

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Trie:

def __init__(self):
"""
"""
self.root = {}

def move(self, word, mod):
cur = self.root
for c in word:
if c not in cur:
if mod != 1:
return False
cur[c] = {}
cur = cur[c]
if mod == 1:
cur['#'] = None
else:
return mod == 3 or '#' in cur

def insert(self, word: str) -> None:
"""
Inserts a word into the trie.
"""
return self.move(word, 1)

def search(self, word: str) -> bool:
"""
Returns if the word is in the trie.
"""
return self.move(word, 2)

def startsWith(self, prefix: str) -> bool:
"""
Returns if there is any word in the trie that starts with the given prefix.
"""
return self.move(prefix, 3)
``````
Copy The Code &

Input

cmd
["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

Output

cmd
[null, null, true, false, true, null, true]

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _0208_ImplementTrie
{
private Node root;

/** Initialize your data structure here. */
public _0208_ImplementTrie()
{
root = new Node();
}

/** Inserts a word into the trie. */
public void Insert(string word)
{
var currentNode = root;

foreach (var ch in word)
{
if (currentNode.Children[ch - 'a'] == null)
currentNode.Children[ch - 'a'] = new Node();
currentNode = currentNode.Children[ch - 'a'];
}

currentNode.IsFinished = true;
}

/** Returns if the word is in the trie. */
public bool Search(string word)
{
var currentNode = root;

foreach (var ch in word)
if (currentNode.Children[ch - 'a'] == null)
return false;
else
currentNode = currentNode.Children[ch - 'a'];

return currentNode.IsFinished;
}

/** Returns if there is any word in the trie that starts with the given prefix. */
public bool StartsWith(string prefix)
{
var currentNode = root;

foreach (var ch in prefix)
if (currentNode.Children[ch - 'a'] == null)
return false;
else
currentNode = currentNode.Children[ch - 'a'];

return true;
}

public class Node
{
public Node[] Children { get; } = new Node[26];

public bool IsFinished { get; set; }
}
}
}
``````
Copy The Code &

Input

cmd
["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

Output

cmd
[null, null, true, false, true, null, true]