Leetcode Medium

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:

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

Solution

class Trie {
  // Nested class for a node in the Trie
  public class TrieNode {
    public boolean isWord;
    public TrieNode[] children;
    public String word;

    public TrieNode () {
      this.isWord = false;
      // 127 is the number of ascii characters in java
      this.children = new TrieNode[127];
    }
  }

  public TrieNode root;

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

  /** Inserts a word into the trie. */
  public void insert(String word) {
    TrieNode tracker = root;

    for (int i = 0; i < word.length(); i++) {
      char curChar = word.charAt(i);

      // If this path has not been seen before
      if (tracker.children[curChar] == null) {
        tracker.children[curChar] = new TrieNode();
      }

      tracker = tracker.children[curChar];
    }

    // We are now at the end of a word
    tracker.isWord = true;
    tracker.word = word;
  }

  /** Returns if the word is in the trie. */
  public boolean search(String word) {
    TrieNode tracker = root;

    for (int i = 0; i < word.length(); i++) {
      char curChar = word.charAt(i);

      // If this path has not been seen before
      if (tracker.children[curChar] == null) {
        return false;
      }

      tracker = tracker.children[curChar];
    }

    return tracker.isWord;
  }

  /** Returns if there is any word in the trie that starts with the given prefix. */
  public boolean startsWith(String prefix) {
    TrieNode tracker = root;

    for (int i = 0; i < prefix.length(); i++) {
      char curChar = prefix.charAt(i);

      // If this path has not been seen before
      if (tracker.children[curChar] == null) {
        return false;
      }

      tracker = tracker.children[curChar];
    }

    return true;
  }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

Why this works

A trie is a data structure that is typically used as a fast way to look up prefixes in a given dictionary. It stores letters as nodes and each path to a leaf node (or any node with isWord = true) represents a word in the dictionary.

insert

The insert method builds the tree one char at a time. If the path has not been been created yet, we will add a new child node that corresponds to the next char in the sequence. Once we are done traversing we set the final node (the leaf) to isWord = True.

search

We traverse the tree one char at a time, and when we are finished traversing the path (if it exists), we check to see that that node represented the ending of a word.

startsWith

We do the same process as search, but don’t check if the ending node is a word or not, because as long as it exists, there are word(s) that use that string as a prefix.