Back to DSA

Implement Trie (Prefix Tree)

medium
Acceptance: 53%
TrieDesignString

A trie (prefix tree) is a specialised tree for storing and looking up strings efficiently. Build a Trie class with three operations: insert(word) adds a word, search(word) returns true only if the exact word exists, and startsWith(prefix) returns true if any stored word begins with the given prefix.

Examples

Example 1:
Input:Trie(), insert('hello'), search('hello'), search('hell'), startsWith('hel'), insert('hell'), search('hell')
Output:[null,null,true,false,true,null,true]

Hints

Related Problems

Min StackmediumValid ParentheseseasyDecode StringmediumOnline Stock SpanmediumBasic Calculatorhard
00:00
class Trie {
    private Trie[] children = new Trie[26];
    private boolean isEnd = false;

    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) {
        return searchPrefix(prefix) != null;
    }

    private Trie searchPrefix(String word) {
        Trie node = this;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) return null;
            node = node.children[idx];
        }
        return node;
    }
}
Time complexityO(m) where m is key length
Space complexityO(n * m)