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 stringwordinto the trie.boolean search(String word)Returnstrueif the stringwordis in the trie (i.e., was inserted before), andfalseotherwise.boolean startsWith(String prefix)Returnstrueif there is a previously inserted stringwordthat has the prefixprefix, andfalseotherwise.
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 <= 2000wordandprefixconsist only of lowercase English letters.- At most
3 * 104calls in total will be made toinsert,search, andstartsWith.
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);
}
Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[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;
}
};
Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[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 < >();
}
}
}
Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]
#4 Code Example with Javascript Programming
Code -
Javascript Programming
s
class Trie {
constructor() {
this.links = new Map();
this.isWord = false;
}
insert(word) {
let node = this;
for (const c of word) {
if (!node.links.has(c)) node.links.set(c, new Trie());
node = node.links.get(c);
}
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) {
if (node.links.has(c)) node = node.links.get(c);
else return null;
}
return node;
}
}
Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]
#5 Code Example with Python Programming
Code -
Python Programming
class Trie:
def __init__(self):
"""
Initialize your data structure here.
"""
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)
Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[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; }
}
}
}
Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]