Problem Description:

Implement a trie with insert, search, and startsWith methods.

Note: You may assume that all inputs are consist of lowercase letters a-z.

Example:

Trie trie = new Trie();

trie.insert("apple");

trie.search("apple"); // returns true

trie.search("app"); // returns false

trie.startsWith("app"); // returns true

trie.insert("app");

trie.search("app"); // returns true

Solution:

A Trie prefix tree is a tree data structure which is used to store the strings. Each node in the Trie represents a character of the string and stores the boolean value to indicate whether it is the end of a word. The Trie tree is used to find all the possible words by traversing all the nodes of the tree. Insertion in the Trie tree is performed by iterating each character of the string and checking if the character is already present in the Trie tree. If it is present, then move to the corresponding node of that character, otherwise create a new node and connect it with the Trie tree.

Algorithm:

The basic steps of the algorithm to create a Trie tree are:

Create a Trie class that contains an array of TrieNode.

Create a TrieNode class that contains an array of TrieNode and a boolean flag to track whether it is the end of the word.

Add methods to the Trie class to insert, search, and startWith.

To insert the string in the Trie tree, move through each character of the string. If the character is not present in the Trie tree, then create a new TrieNode with the character as the value of the TrieNode. Continue until the entire string is traversed.

At the end of the last character, set the boolean flag of the TrieNode to true.

To search for a string in the Trie tree, iterate each character of the string and check if the corresponding TrieNode of that character is present. If it is present, then move to the corresponding node of that character.

After iterating through all the characters of the string, return true if the final TrieNode boolean flag is true, otherwise false.

To startWith a string in the Trie tree, iterate through each character of the string and check if the corresponding TrieNode of that character is present. If it is present, then move to the corresponding node of that character.

After iterating through all the characters of the string, return true.

Code in Python:

class TrieNode: def init(self): self.children = [None]*26 self.isEndOfWord = False

class Trie: def init(self): self.root = TrieNode()

def insert(self, word: str) -> None:
    node = self.root
    for c in word:
        index = ord(c)-ord('a')
        if not node.children[index]:
            node.children[index] = TrieNode()
        node = node.children[index]
    node.isEndOfWord = True

def search(self, word: str) -> bool:
    node = self.root
    for c in word:
        index = ord(c)-ord('a')
        if not node.children[index]:
            return False
        node = node.children[index]
    return node.isEndOfWord

def startsWith(self, prefix: str) -> bool:
    node = self.root
    for c in prefix:
        index = ord(c)-ord('a')
        if not node.children[index]:
            return False
        node = node.children[index]
    return True

main function

if name == 'main': trie = Trie() trie.insert("apple") print(trie.search("apple")) # returns true print(trie.search("app")) # returns false print(trie.startsWith("app")) # returns true trie.insert("app") print(trie.search("app")) # returns true

The above code creates a Trie tree and adds the string 'apple'. The search operation is performed to check if the string 'apple' is present in the Trie tree or not. The startsWith operation is performed to check if the character 'a' is starting with in the Trie tree or not. The Trie tree is then updated by adding the string 'app'. Again the search operation is performed to check if the string 'app' is present in the Trie tree or not.

1