Last updated on February 2nd, 2025 at 06:39 am

Here, we see a Implement Trie (Prefix Tree) LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Design, Trie

Companies

Bloomberg, Facebook, Google, Microsoft, Twitter, Uber

Level of Question

Medium

Implement Trie (Prefix Tree) LeetCode Solution

1. 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:
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

2. Coding Pattern Used in Solution

The provided code implements a Trie (Prefix Tree) data structure, which is commonly used for problems involving string manipulation, prefix matching, and efficient storage/retrieval of strings.

3. Code Implementation in Different Languages

3.1 Implement Trie (Prefix Tree) C++

class TrieNode {
public:
    TrieNode *child[26];
    bool isWord;
    TrieNode() {
        isWord = false;
        for (auto &a : child) a = nullptr;
    }
};
class Trie {
    TrieNode* root;
public:
    Trie() {
        root = new TrieNode();
    }
    void insert(string s) {
        TrieNode *p = root;
        for (auto &a : s) {
            int i = a - 'a';
            if (!p->child[i]) p->child[i] = new TrieNode();
            p = p->child[i];
        }
        p->isWord = true;
    }
    bool search(string key, bool prefix=false) {
        TrieNode *p = root;
        for (auto &a : key) {
            int i = a - 'a';
            if (!p->child[i]) return false;
            p = p->child[i];
        }
        if (prefix==false) return p->isWord;
        return true;
    }
    bool startsWith(string prefix) {
        return search(prefix, true);
    }
};

3.2 Implement Trie (Prefix Tree) Java

class Trie {
    Node root;

    public Trie() {
        root = new Node();
    }
    
    public void insert(String word) {
        root.insert(word, 0);
    }
    
    public boolean search(String word) {
        return root.search(word, 0);
    }
    
    public boolean startsWith(String prefix) {
        return root.startsWith(prefix, 0);
    }

    class Node {
        Node[] nodes;
        boolean isEnd;

        Node() {
            nodes = new Node[26];
        }

        private void insert(String word, int idx) {
            if (idx >= word.length()) return;
            int i = word.charAt(idx) - 'a';
            if (nodes[i] == null) {
                nodes[i] = new Node();
            }

            if (idx == word.length()-1) nodes[i].isEnd = true;
            nodes[i].insert(word, idx+1);
        }

        private boolean search(String word, int idx) {
            if (idx >= word.length()) return false;
            Node node = nodes[word.charAt(idx) - 'a'];
            if (node == null) return false;
            if (idx == word.length() - 1 && node.isEnd) return true;

            return node.search(word, idx+1);

        }

        private boolean startsWith(String prefix, int idx) {
            if (idx >= prefix.length()) return false;
            Node node = nodes[prefix.charAt(idx) - 'a'];
            if (node == null) return false;
            if (idx == prefix.length() - 1) return true;

            return node.startsWith(prefix, idx+1);
        }
    }
}

3.3 Implement Trie (Prefix Tree) JavaScript

var Trie = function() {
    this.root = {};
};

Trie.prototype.insert = function(word) {
    let node = this.root;
    word.split('').forEach((char)=>{
        if (!node[char]) node[char] = {};
        node = node[char];
    })
    node.isEnd = true;
};

Trie.prototype.search = function(word) {
    let node = this.searchNode(word);
    return node!=null?node.isEnd==true:false;
};

Trie.prototype.startsWith = function(prefix) {
    let node = this.searchNode(prefix);
    return node != null;
};

Trie.prototype.searchNode = function(word) {
    let node = this.root;
    for (let char of word.split('')) {
        if (node[char]) {
            node = node[char]
        } else {
            return null;
        }
    }
    return node;
}

3.4 Implement Trie (Prefix Tree) Python

class Trie:
    def __init__(self):
        self.root={}
        
    def insert(self, word) :
        cur=self.root
        for letter in word:
            if letter not in cur:
                cur[letter]={}
            cur=cur[letter]
        cur['*']=''

    def search(self, word):
        cur=self.root
        for letter in word:
            if letter not in cur:
                return False
            cur=cur[letter]
        return '*' in cur
        
    def startsWith(self, prefix):
        cur=self.root
        for letter in prefix:
            if letter not in cur:
                return False
            cur=cur[letter]
        return True

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(L)	O(N * L)
Java	O(L)	O(N * L)
JavaScript	O(L)	O(N * L)
Python	O(L)	O(N * L)

where, N is the number of words inserted into the Trie, and L is the average length of the words.