Implement Trie (Prefix Tree)

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.

Link: https://leetcode.com/problems/implement-trie-prefix-tree/

Problem Explanation with examples:-

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 * 10<sup>4</sup> calls in total will be made to insert, search, and startsWith.

Intuition:-

• We can use a list or hash table to store the words.

• For search, we can just check if the word is in the list or hash table.

• For startsWith, we can check if the prefix is the prefix of any word in the list or hash table.

• It's a simple straightforward solution.

Solution:-

• Initialize a list to store the words in the constructor.

• For insert, we can just append the word to the list.

• For search, we can just check if the word is in the list and return True or False.

• For startsWith, traverse the list and check every word if it starts with the prefix. If it does, return True. In the end, return False.

Code:-

JAVA Solution

public class Trie {
    private List<String> trie;

    public Trie() {
        trie = new ArrayList<>();
    }

    public void insert(String word) {
        trie.add(word);
    }

    public boolean search(String word) {
        return trie.contains(word);
    }

    public boolean startsWith(String prefix) {
        int n = prefix.length();
        for (String word : trie) {
            if (word.length() >= n && word.substring(0, n).equals(prefix)) {
                return true;
            }
        }
        return false;
    }
}

Python Solution

class Trie:

    def __init__(self):
        self.trie = []


    def insert(self, word: str) -> None:
        self.trie.append(word)


    def search(self, word: str) -> bool:
        return word in self.trie


    def startsWith(self, prefix: str) -> bool:
        n = len(prefix)
        for i in self.trie:
            if prefix == i[:n]:
                return True
        return False

Complexity Analysis:-

TIME:-

• The insert method has a time complexity of O(1) because it simply appends the word to the end of the list.

• The search method has a time complexity of O(n), where n is the number of words in the trie because it checks if the given word is present in the list by iterating over all the words.

• The startsWith method has a time complexity of O(n), where n is the number of words in the trie because it checks if any word in the list starts with the given prefix by iterating over all the words and comparing their prefixes with the given prefix.

SPACE:-

• The space complexity of the Trie class is O(n*m), where n is the number of words inserted and m is the average length of the words because it stores all the words in a list.

• In addition, there is also some overhead space required to store the Trie object itself and any other internal data structures used by Python to manage the list.

References:-

• Recursion

• Trie

• Classes and Objects

Connect with me:-

• Twitter

• Github

• LinkedIn