LeetCode 0208. Implement Trie (Prefix Tree) Solution in Java, C++, Python & More | Explanation + Code

Description

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.

Solutions

Solution 1: Trie (Prefix Tree)

Each node in the trie contains two parts:

1. An array of pointers to child nodes children. For this problem, the array length is 26, representing the number of lowercase English letters. children[0] corresponds to lowercase letter 'a', ..., and children[25] corresponds to lowercase letter 'z'.
2. A boolean field isEnd indicating whether the node is the end of a string.

1. Insert a String

We start from the root of the trie and insert the string. For the child node corresponding to the current character, there are two cases:

• The child node exists. Move along the pointer to the child node and continue processing the next character.
• The child node does not exist. Create a new child node, record it in the corresponding position of the children array, then move along the pointer to the child node and continue searching for the next character.

Repeat the above steps until the last character of the string is processed, then mark the current node as the end of the string.

2. Search for a Prefix

We start from the root of the trie and search for the prefix. For the child node corresponding to the current character, there are two cases:

• The child node exists. Move along the pointer to the child node and continue searching for the next character.
• The child node does not exist. This means the trie does not contain the prefix, so return a null pointer.

Repeat the above steps until a null pointer is returned or the last character of the prefix is searched.

If we search to the end of the prefix, it means the trie contains the prefix. Additionally, if the isEnd of the node corresponding to the end of the prefix is true, it means the trie contains the string.

The time complexity for inserting a string is O(m × |Σ|), and the time complexity for searching a prefix is O(m), where m is the length of the string and |Σ| is the size of the character set (26 in this problem). The space complexity is O(q × m × |Σ|), where q is the number of inserted strings.

PythonJavaC++GoTypeScriptRustJavaScriptC#

class Trie: def __init__(self): self.children = [None] * 26 self.is_end = False def insert(self, word: str) -> None: node = self for c in word: idx = ord(c) - ord('a') if node.children[idx] is None: node.children[idx] = Trie() node = node.children[idx] node.is_end = True def search(self, word: str) -> bool: node = self._search_prefix(word) return node is not None and node.is_end def startsWith(self, prefix: str) -> bool: node = self._search_prefix(prefix) return node is not None def _search_prefix(self, prefix: str): node = self for c in prefix: idx = ord(c) - ord('a') if node.children[idx] is None: return None node = node.children[idx] return node # Your Trie object will be instantiated and called as such: # obj = Trie() # obj.insert(word) # param_2 = obj.search(word) # param_3 = obj.startsWith(prefix)(code-box)

class Trie { private Trie[] children; private boolean isEnd; public Trie() { children = new Trie[26]; } public void insert(String word) { Trie node = this; for (char c : word.toCharArray()) { int idx = c - 'a'; if (node.children[idx] == null) { node.children[idx] = new Trie(); } node = node.children[idx]; } node.isEnd = true; } public boolean search(String word) { Trie node = searchPrefix(word); return node != null && node.isEnd; } public boolean startsWith(String prefix) { Trie node = searchPrefix(prefix); return node != null; } private Trie searchPrefix(String s) { Trie node = this; for (char c : s.toCharArray()) { int idx = c - 'a'; if (node.children[idx] == null) { return null; } node = node.children[idx]; } return node; } } /** * Your Trie object will be instantiated and called as such: * Trie obj = new Trie(); * obj.insert(word); * boolean param_2 = obj.search(word); * boolean param_3 = obj.startsWith(prefix); */(code-box)

class Trie { private: vector<Trie*> children; bool isEnd; Trie* searchPrefix(string s) { Trie* node = this; for (char c : s) { int idx = c - 'a'; if (!node->children[idx]) return nullptr; node = node->children[idx]; } return node; } public: Trie() : children(26) , isEnd(false) {} void insert(string word) { Trie* node = this; for (char c : word) { int idx = c - 'a'; if (!node->children[idx]) node->children[idx] = new Trie(); node = node->children[idx]; } node->isEnd = true; } bool search(string word) { Trie* node = searchPrefix(word); return node != nullptr && node->isEnd; } bool startsWith(string prefix) { Trie* node = searchPrefix(prefix); return node != nullptr; } }; /** * Your Trie object will be instantiated and called as such: * Trie* obj = new Trie(); * obj->insert(word); * bool param_2 = obj->search(word); * bool param_3 = obj->startsWith(prefix); */(code-box)

type Trie struct { children [26]*Trie isEnd bool } func Constructor() Trie { return Trie{} } func (this *Trie) Insert(word string) { node := this for _, c := range word { idx := c - 'a' if node.children[idx] == nil { node.children[idx] = &Trie{} } node = node.children[idx] } node.isEnd = true } func (this *Trie) Search(word string) bool { node := this.SearchPrefix(word) return node != nil && node.isEnd } func (this *Trie) StartsWith(prefix string) bool { node := this.SearchPrefix(prefix) return node != nil } func (this *Trie) SearchPrefix(s string) *Trie { node := this for _, c := range s { idx := c - 'a' if node.children[idx] == nil { return nil } node = node.children[idx] } return node } /** * Your Trie object will be instantiated and called as such: * obj := Constructor(); * obj.Insert(word); * param_2 := obj.Search(word); * param_3 := obj.StartsWith(prefix); */(code-box)

class TrieNode { children; isEnd; constructor() { this.children = new Array(26); this.isEnd = false; } } class Trie { root; constructor() { this.root = new TrieNode(); } insert(word: string): void { let head = this.root; for (let char of word) { let index = char.charCodeAt(0) - 97; if (!head.children[index]) { head.children[index] = new TrieNode(); } head = head.children[index]; } head.isEnd = true; } search(word: string): boolean { let head = this.searchPrefix(word); return head != null && head.isEnd; } startsWith(prefix: string): boolean { return this.searchPrefix(prefix) != null; } private searchPrefix(prefix: string) { let head = this.root; for (let char of prefix) { let index = char.charCodeAt(0) - 97; if (!head.children[index]) return null; head = head.children[index]; } return head; } }(code-box)

use std::{cell::RefCell, collections::HashMap, rc::Rc}; struct TrieNode { pub val: Option<char>, pub flag: bool, pub child: HashMap<char, Rc<RefCell<TrieNode>>>, } impl TrieNode { fn new() -> Self { Self { val: None, flag: false, child: HashMap::new(), } } fn new_with_val(val: char) -> Self { Self { val: Some(val), flag: false, child: HashMap::new(), } } } struct Trie { root: Rc<RefCell<TrieNode>>, } /// Your Trie object will be instantiated and called as such: /// let obj = Trie::new(); /// obj.insert(word); /// let ret_2: bool = obj.search(word); /// let ret_3: bool = obj.starts_with(prefix); impl Trie { fn new() -> Self { Self { root: Rc::new(RefCell::new(TrieNode::new())), } } fn insert(&self, word: String) { let char_vec: Vec<char> = word.chars().collect(); // Get the clone of current root node let mut root = Rc::clone(&self.root); for c in &char_vec { if !root.borrow().child.contains_key(c) { // We need to manually create the entry root.borrow_mut() .child .insert(*c, Rc::new(RefCell::new(TrieNode::new()))); } // Get the child node let root_clone = Rc::clone(root.borrow().child.get(c).unwrap()); root = root_clone; } { root.borrow_mut().flag = true; } } fn search(&self, word: String) -> bool { let char_vec: Vec<char> = word.chars().collect(); // Get the clone of current root node let mut root = Rc::clone(&self.root); for c in &char_vec { if !root.borrow().child.contains_key(c) { return false; } // Get the child node let root_clone = Rc::clone(root.borrow().child.get(c).unwrap()); root = root_clone; } let flag = root.borrow().flag; flag } fn starts_with(&self, prefix: String) -> bool { let char_vec: Vec<char> = prefix.chars().collect(); // Get the clone of current root node let mut root = Rc::clone(&self.root); for c in &char_vec { if !root.borrow().child.contains_key(c) { return false; } // Get the child node let root_clone = Rc::clone(root.borrow().child.get(c).unwrap()); root = root_clone; } true } }(code-box)

/** * Initialize your data structure here. */ var Trie = function () { this.children = {}; }; /** * Inserts a word into the trie. * @param {string} word * @return {void} */ Trie.prototype.insert = function (word) { let node = this.children; for (let char of word) { if (!node[char]) { node[char] = {}; } node = node[char]; } node.isEnd = true; }; /** * Returns if the word is in the trie. * @param {string} word * @return {boolean} */ Trie.prototype.search = function (word) { let node = this.searchPrefix(word); return node != undefined && node.isEnd != undefined; }; Trie.prototype.searchPrefix = function (prefix) { let node = this.children; for (let char of prefix) { if (!node[char]) return false; node = node[char]; } return node; }; /** * Returns if there is any word in the trie that starts with the given prefix. * @param {string} prefix * @return {boolean} */ Trie.prototype.startsWith = function (prefix) { return this.searchPrefix(prefix); }; /** * Your Trie object will be instantiated and called as such: * var obj = new Trie() * obj.insert(word) * var param_2 = obj.search(word) * var param_3 = obj.startsWith(prefix) */(code-box)

public class Trie { bool isEnd; Trie[] children = new Trie[26]; public Trie() { } public void Insert(string word) { Trie node = this; foreach (var c in word) { var idx = c - 'a'; node.children[idx] ??= new Trie(); node = node.children[idx]; } node.isEnd = true; } public bool Search(string word) { Trie node = SearchPrefix(word); return node != null && node.isEnd; } public bool StartsWith(string prefix) { Trie node = SearchPrefix(prefix); return node != null; } private Trie SearchPrefix(string s) { Trie node = this; foreach (var c in s) { var idx = c - 'a'; if (node.children[idx] == null) { return null; } node = node.children[idx]; } return node; } } /** * Your Trie object will be instantiated and called as such: * Trie obj = new Trie(); * obj.Insert(word); * bool param_2 = obj.Search(word); * bool param_3 = obj.StartsWith(prefix); */(code-box)