Implement Trie Ii Prefix Tree - Leetcode Solution

Problem:

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

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

Note:

1. You may assume that all inputs are consist of lowercase letters a-z.
2. All inputs are guaranteed to be non-empty strings.

Solution:

Trie, also known as Prefix tree, is an important data structure used for querying strings. Trie is useful for solving problems related to string searching, prefix searching etc.

In this problem, we need to implement a trie that supports three operations - insert, search, and startsWith.

Insert operation: When a string is to be inserted into the trie, it should be added at a position in the trie such that, each node in the trie represents a character in the string being inserted. If a node representing a character in the string does not exist, it should be created and attached to the parent node. To mark the end of a string in trie, we can use a boolean flag at the node representing the last character of the string.

Search operation: When a string is to be searched in the trie, we traverse the trie nodes along the characters of the string. If at any point, a node representing the character in the string is not found, then the string is not present in the trie. If the last character of the string is found, and the boolean flag at that node is true, then the string is present in the trie.

StartsWith operation: When a string prefix is to be searched in the trie, we traverse the trie nodes along the characters of the prefix. If at any point, a node representing the character is not found, then the prefix is not present in the trie. If all characters of the prefix are found, then the prefix is present in the trie.

To implement the above operations, we can define a trie node as follows:

class TrieNode { boolean isEndOfWord; TrieNode[] children; TrieNode() { isEndOfWord = false; children = new TrieNode[26]; } }

Here, each node of the trie represents a lowercase character, and the 'isEndOfWord' flag indicates if this node is the end of a string in the trie. The 'children' array represents the edges from this node to the child nodes in the trie.

The following code implements the Trie class:

class Trie { private TrieNode root; /** Initialize your data structure here. */ public Trie() { root = new TrieNode(); }

/** Inserts a word into the trie. */
public void insert(String word) {
    TrieNode curr = root;
    for (char c : word.toCharArray()) {
        int index = c - 'a';
        if (curr.children[index] == null) {
            curr.children[index] = new TrieNode();
        }
        curr = curr.children[index];
    }
    curr.isEndOfWord = true;
}

/** Returns if the word is in the trie. */
public boolean search(String word) {
    TrieNode curr = root;
    for (char c : word.toCharArray()) {
        int index = c - 'a';
        if (curr.children[index] == null) {
            return false;
        }
        curr = curr.children[index];
    }
    return curr.isEndOfWord;
}

/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
    TrieNode curr = root;
    for (char c : prefix.toCharArray()) {
        int index = c - 'a';
        if (curr.children[index] == null) {
            return false;
        }
        curr = curr.children[index];
    }
    return true;
}

}

In the insert() operation, we traverse the trie based on the characters of the string to be inserted, and create new nodes in the trie as necessary. Finally, we set the 'isEndOfWord' flag for the last node of the string.

In the search() operation, we traverse the trie based on the characters of the string being searched, and return false if any node representing a character in the string does not exist. If the last character of the string is found in the trie, then we check if the 'isEndOfWord' flag is set at that node or not.

In the startsWith() operation, we traverse the trie based on the characters of the prefix string, and return false if any node representing a character in the prefix string does not exist. If all characters of the prefix string are found in the trie, then the prefix is present in the trie.

Time complexity: Insert operation takes O(L) time, where L is the length of the string being inserted. Search and startsWith operation takes O(L) time, where L is the length of the string/prefix being searched. The space complexity of this implementation is O(ALPHABET_SIZE * N * L), where ALPHABET_SIZE is the number of characters in the alphabet (26 for English alphabets), N is the number of strings in the trie, and L is the average length of each string in the trie.

1