208. Implement Trie (Prefix Tree)

Posted on 3 mins read

1. Description

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.

2. Example

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

3. Constraints

  • 1 <= word.length, prefix.length <= 2000
  • word and prefix consist only of lowercase English letters.
  • At most $3 * 10^4$ calls in total will be made to insert, search, and startsWith.

4. Solutions

My Accepted Solution(Follow Up)

n is the number of nodes in m_head
Time complexity(Trie()): O(1)
Time complexity(insert(word)): O(word.size())
Time complexity(search(word)): O(word.size())
Time complexity(startsWith(prefix)): O(prefix.size())
Space complexity(Trie()): O(1)
Space complexity(insert(word)): O(word.size())
Space complexity(search(word)): O(1)
Space complexity(startsWith(prefix)): O(1)

class TrieNode {
public:
    array<TrieNode*, 26> childs;  // 26 lower case letters
    bool isEnd;

    TrieNode() : isEnd(false) {
        for (int i = 0; i < childs.size(); ++i) {
            childs[i] = nullptr;
        }
    }
};

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

    /** Inserts a word into the trie. */
    // void insert(string word)
    void insert(const string& i_word) {
        auto iter = head;
        for (auto letter : i_word) {
            if (iter->childs[getLetterIndex(letter)] == nullptr) {
                iter->childs[getLetterIndex(letter)] = new TrieNode();
            }

            iter = iter->childs[getLetterIndex(letter)];
        }

        iter->isEnd = true;
    }

    /** Returns if the word is in the trie. */
    // bool search(string word)
    bool search(const string& i_word) {
        auto iter = head;
        for (auto letter : i_word) {
            if (iter->childs[getLetterIndex(letter)] == nullptr) {
                return false;
            }

            iter = iter->childs[getLetterIndex(letter)];
        }

        return iter->isEnd;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    // bool startsWith(string prefix)
    bool startsWith(const string& i_prefix) {
        auto iter = head;
        for (auto letter : i_prefix) {
            if (iter->childs[getLetterIndex(letter)] == nullptr) {
                return false;
            }

            iter = iter->childs[getLetterIndex(letter)];
        }

        return true;
    }

private:
    TrieNode* head;

    int getLetterIndex(char letter) {
        return letter - 'a';
    }
};
comments powered by Disqus