Follow

# Leeting-LCS

Follow # Implement Trie (Prefix Tree)

## Leetcode Daily Challenge (17th March, 2023)

Lakshit Chiranjiv Sagar
·Mar 17, 2023·

• Problem Statement:-
• Problem Explanation with examples:-
• Intuition:-
• Solution:-
• Code:-
• Complexity Analysis:-
• References:-
• Connect with me:-

### 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.

### 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) {
}

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.