Problem Statement:
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
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.
Approach
- We use a Trie (Prefix Tree) to store words character by character.
- Each node represents a character and contains:
children:links to next characters.isEndOfWord:marks completion of a word.
- Insertion (insert)
- Start from the root.
- For each character in the word:
- If the character node doesn’t exist, create it.
- Move to that node.
- After the last character, mark
isEndOfWord = true. - Search (search)
- Start from the root.
- Traverse characters of the word.
- If any character is missing, the word doesn’t exist.
- If traversal ends and isEndOfWord is true, the word exists.
- Prefix Check (
startsWith) - Start from the root.
- Traverse characters of the prefix.
- If all characters exist, the prefix is present (no need to check isEndOfWord).
Time Complexity:
Insertion → O(L) where: 'L' length of the word.
Search → O(L)
Prefix → O(P)
Space Complexity:
Insertion → O(N x L)
Search → O(1)
Dry Run
Input:
Operations: insert("cat") insert("car") search("cat") search("cap") startsWith("ca") State Transitions:
Initially: root = {}
insert("cat"): curr = root
char = 'c' → not present → create TrieNode, move to children['c']
char = 'a' → not present → create TrieNode, move to children['a']
char = 't' → not present → create TrieNode, move to children['t']
Mark isEndOfWord = true at 't'
Trie structure: c → a → t (end)
insert("car"): curr = root
char = 'c' → exists → move
char = 'a' → exists → move
char = 'r' → not present → create TrieNode, move
Mark isEndOfWord = true at 'r'
Trie structure: c → a → t (end), a → r (end)
search("cat"): curr = root
char = 'c' → exists → move
char = 'a' → exists → move
char = 't' → exists → move
isEndOfWord = true → Returns: true
search("cap"): curr = root
char = 'c' → exists → move
char = 'a' → exists → move
char = 'p' → NOT present → Returns: false
startsWith("ca"): curr = root
char = 'c' → exists → move
char = 'a' → exists → move
All prefix characters found → Returns: true
Final State: Stored words in Trie: "cat", "car". Prefix "ca" exists, but "cap" does not.
class TrieNode {
constructor() {
this.children = {};
this.isEndOfWord = false;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(word) {
let curr = this.root;
for (let char of word) {
if (!curr.children[char]) {
curr.children[char] = new TrieNode();
}
curr = curr.children[char];
}
curr.isEndOfWord = true;
}
search(word) {
let curr = this.root;
for (let char of word) {
if (!curr.children[char]) {
return false;
}
curr = curr.children[char];
}
return curr.isEndOfWord;
}
startsWith(prefix) {
let curr = this.root;
for (let char of prefix) {
if (!curr.children[char]) {
return false;
}
curr = curr.children[char];
}
return true;
}
}
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
curr = self.root
for char in word:
if char not in curr.children:
curr.children[char] = TrieNode()
curr = curr.children[char]
curr.is_end_of_word = True
def search(self, word: str) -> bool:
curr = self.root
for char in word:
if char not in curr.children:
return False
curr = curr.children[char]
return curr.is_end_of_word
def startsWith(self, prefix: str) -> bool:
curr = self.root
for char in prefix:
if char not in curr.children:
return False
curr = curr.children[char]
return True
import java.util.HashMap;
import java.util.Map;
class TrieNode {
Map children = new HashMap<>();
boolean isEndOfWord = false;
}
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode curr = root;
for (char c : word.toCharArray()) {
curr.children.putIfAbsent(c, new TrieNode());
curr = curr.children.get(c);
}
curr.isEndOfWord = true;
}
public boolean search(String word) {
TrieNode curr = root;
for (char c : word.toCharArray()) {
if (!curr.children.containsKey(c)) {
return false;
}
curr = curr.children.get(c);
}
return curr.isEndOfWord;
}
public boolean startsWith(String prefix) {
TrieNode curr = root;
for (char c : prefix.toCharArray()) {
if (!curr.children.containsKey(c)) {
return false;
}
curr = curr.children.get(c);
}
return true;
}
}
#include <unordered_map>
#include <string>
using namespace std;
class TrieNode {
public:
unordered_map children;
bool isEndOfWord;
TrieNode() {
isEndOfWord = false;
}
};
class Trie {
private:
TrieNode* root;
public:
Trie() {
root = new TrieNode();
}
void insert(string word) {
TrieNode* curr = root;
for (char c : word) {
if (!curr->children[c]) {
curr->children[c] = new TrieNode();
}
curr = curr->children[c];
}
curr->isEndOfWord = true;
}
bool search(string word) {
TrieNode* curr = root;
for (char c : word) {
if (!curr->children[c]) {
return false;
}
curr = curr->children[c];
}
return curr->isEndOfWord;
}
bool startsWith(string prefix) {
TrieNode* curr = root;
for (char c : prefix) {
if (!curr->children[c]) {
return false;
}
curr = curr->children[c];
}
return true;
}
};
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define ALPHABET_SIZE 26
typedef struct TrieNode {
struct TrieNode* children[ALPHABET_SIZE];
bool isEndOfWord;
} TrieNode;
TrieNode* createNode() {
TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
node->isEndOfWord = false;
for (int i = 0; i < ALPHABET_SIZE; i++) {
node->children[i] = NULL;
}
return node;
}
void insert(TrieNode* root, const char* word) {
TrieNode* curr = root;
while (*word) {
int index = *word - 'a';
if (!curr->children[index]) {
curr->children[index] = createNode();
}
curr = curr->children[index];
word++;
}
curr->isEndOfWord = true;
}
bool search(TrieNode* root, const char* word) {
TrieNode* curr = root;
while (*word) {
int index = *word - 'a';
if (!curr->children[index]) {
return false;
}
curr = curr->children[index];
word++;
}
return curr->isEndOfWord;
}
bool startsWith(TrieNode* root, const char* prefix) {
TrieNode* curr = root;
while (*prefix) {
int index = *prefix - 'a';
if (!curr->children[index]) {
return false;
}
curr = curr->children[index];
prefix++;
}
return true;
}
using System.Collections.Generic;
public class TrieNode {
public Dictionary children = new Dictionary();
public bool isEndOfWord = false;
}
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void Insert(string word) {
TrieNode curr = root;
foreach (char c in word) {
if (!curr.children.ContainsKey(c)) {
curr.children[c] = new TrieNode();
}
curr = curr.children[c];
}
curr.isEndOfWord = true;
}
public bool Search(string word) {
TrieNode curr = root;
foreach (char c in word) {
if (!curr.children.ContainsKey(c)) {
return false;
}
curr = curr.children[c];
}
return curr.isEndOfWord;
}
public bool StartsWith(string prefix) {
TrieNode curr = root;
foreach (char c in prefix) {
if (!curr.children.ContainsKey(c)) {
return false;
}
curr = curr.children[c];
}
return true;
}
}
