Insert & Search in Trie
Problem Statement
Implement a Trie with insert and search functionality for lowercase English words.
Example: Insert: ["apple","app"], Search: "app" → true, "appl" → false
Approach: Trie Node Insertion & Search
Explanation: Each node stores children and an end-of-word flag. Insert characters sequentially. Search checks path exists and word ends correctly.
Time Complexity: O(L), L = length of word
Space Complexity: O(N*L), N = number of words
class TrieNode:
children = {}
isEnd = False
class Trie:
root = TrieNode()
insert(word):
node = root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.isEnd = True
search(word):
node = root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.isEnd
💡 Think: Walk characters creating child nodes as needed; to search, follow the path and check end-of-word.