Implement Trie Prefix Tree

Question

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:

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

Solution

from typing import *
class TrieNode:
    val: int
    neighbours: Dict[str, 'TrieNode']
    isWord: bool

    def __init__(self, val: str):
        self.val = val
        self.neighbours = {} #  { a: TrieNode(a) } 
        self.isWord = False

class Trie:
    def __init__(self):
        self.root = TrieNode("*")        

    def insert(self, word: str) -> None:
        currNode = self.root
        for letter in word:
            if letter not in currNode.neighbours:
                currNode.neighbours[letter] = TrieNode(letter)
            currNode = currNode.neighbours[letter]
        currNode.isWord = True

    def search(self, word: str) -> bool:
        currNode = self.root
        for letter in word:
            if letter not in currNode.neighbours:
                return False
            
            currNode = currNode.neighbours[letter]
        
        return currNode.isWord
        
    def startsWith(self, prefix: str) -> bool:
        currNode = self.root
        for letter in prefix:
            if letter not in currNode.neighbours:
                return False
            currNode = currNode.neighbours[letter]
        return True

Time complexity: $O(L)$ — $L$ is the length of the longest word

Space complexity: $O(L)$ — $L$ is the lenght of the longest word, $L$ is the length of the tree

Recursively Search

def search(self, word: str) -> bool:
	return self.recursiveSearch(word, 0, self.root)

def recursiveSearch(self, word: str, index: int, node: TrieNode) -> bool:
	if index >= len(word): return False

	letter = word[index]
	if letter not in node.neighbours: return False

	letterNode = node.neighbours[letter]
	if index == len(word) - 1 and letterNode.isWord:
		return True
	
	return self.recursiveSearch(word, index + 1, letterNode)

Recursively startWith

def startsWith(self, prefix: str) -> bool:
	return self.recursiveStartWith(prefix, 0, self.root)

def recursiveStartWith(self, prefix, index, node) -> bool:
	if index >= len(prefix): return False

	letter = prefix[index]
	if letter not in node.neighbours: return False

	if index == len(prefix) - 1:
		return True
	
	letterNode = node.neighbours[letter]
	return self.recursiveStartWith(prefix, index + 1, letterNode)