DEBUG_INFO: title=Trie, type=object, isArray=, length=21
Implement Trie (Prefix Tree)
Implement a trie which supports insert, search, and startsWith operations.
Examples
Input: ["Trie", "insert", "search", "search", "startsWith"]
[[], ["apple"], ["apple"], ["app"], ["app"]]
Output: [null, null, true, false, true]
Approach 1
Level I: HashMap-based Trie
Intuition
Flexible implementation using a HashMap for children, suitable for any character set (Unicode).
⏱ O(L)💾 O(N * L)
Detailed Dry Run
Insert 'apple': R -> a -> p -> p -> l -> e (end).
import java.util.*;
class Trie {
class Node { Map<Character, Node> children = new HashMap<>(); boolean isEnd = false; }
Node root = new Node();
public void insert(String w) { Node c=root; for(char x:w.toCharArray()) { c.children.putIfAbsent(x, new Node()); c=c.children.get(x); } c.isEnd=true; }
public boolean search(String w) { Node n=find(w); return n!=null && n.isEnd; }
public boolean startsWith(String p) { return find(p)!=null; }
private Node find(String s) { Node c=root; for(char x:s.toCharArray()) { c=c.children.get(x); if(c==null) return null; } return c; }
}
Approach 2
Level III: Array-based Trie (Optimal)
Intuition
Static array [26] for lowercase English. Fastest possible access with minimal memory overhead for dense tries.
⏱ O(L)💾 O(N * L * 26)
Detailed Dry Run
Insert 'cat': root.children['c'-'a'] -> node1.children['a'-'a'] -> node2.children['t'-'a'] -> node3(isEnd=true).
class Trie {\n class Node { Node[] children = new Node[26]; boolean isEnd = false; }\n Node root = new Node();\n public void insert(String w) { Node c=root; for(char x:w.toCharArray()) { int i=x-'a'; if(c.children[i]==null) c.children[i]=new Node(); c=c.children[i]; } c.isEnd=true; }\n public boolean search(String w) { Node n=find(w); return n!=null && n.isEnd; }\n public boolean startsWith(String p) { return find(p)!=null; }\n private Node find(String s) { Node c=root; for(char x:s.toCharArray()) { int i=x-'a'; if(c.children[i]==null) return null; c=c.children[i]; } return c; }\n}