Guidelines

Trie are probably one of the most straighforward patterns to spot since your first hint when working with strings, suffix, prefix should be to use trie data structure. Below we list implementation of basic implementation for trie.

Java

class Trie {
  private class TrieNode{
      TrieNode[] children;
      boolean isWord = false;
      public TrieNode(){
          children = new TrieNode[26];
      }
  }

  TrieNode root;
  public Trie() {
      root = new TrieNode();
  }

  private TrieNode searchPrefix(String prefix){
      TrieNode iter = root;
      for(int i = 0; i < prefix.length(); ++i){
          char letter = prefix.charAt(i);
          if(iter.children[letter - 'a'] == null){
              return null;
          }
          iter = iter.children[letter - 'a'];
      }
      return iter;
  }

  public void insert(String word) {
      TrieNode iter = root;
      for(int i = 0; i < word.length(); ++i){
          char letter = word.charAt(i);
          if(iter.children[letter - 'a'] == null){
              iter.children[letter - 'a'] = new TrieNode();
          }
          iter = iter.children[letter - 'a'];
      }
      iter.isWord = true;
  }

  public boolean search(String word) {
      TrieNode node = searchPrefix(word);
      return node != null && node.isWord;
  }

  public boolean startsWith(String prefix) {
      return searchPrefix(prefix) != null;
  }
}

JavaScript

var Trie = function () {
  this.root = new TrieNode();
};

/**
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function (word) {
  let iter = this.root;
  for (let i = 0; i < word.length; ++i) {
    const letter = word.charAt(i);
    if (!iter.children[letter]) {
      iter.children[letter] = new TrieNode();
    }
    iter = iter.children[letter];
  }
  iter.isWord = true;
};

/**
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function (word) {
  const node = this.searchPrefix(word);
  return node !== null && node.isWord;
};

/**
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function (prefix) {
  return this.searchPrefix(prefix) !== null;
};

Trie.prototype.searchPrefix = function (prefix) {
  let iter = this.root;
  for (let i = 0; i < prefix.length; ++i) {
    const letter = prefix.charAt(i);
    if (!iter.children[letter]) {
      return null;
    }
    iter = iter.children[letter];
  }
  return iter;
};

class TrieNode {
  constructor() {
    this.children = {};
    this.isWord = false;
  }
}

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

Python

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

    def searchPrefix(self, prefix):
        iter = self.root
        for letter in prefix:
            if letter not in iter.children:
                return None
            iter = iter.children[letter]
        return iter


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


    def search(self, word: str) -> bool:
      node = self.searchPrefix(word)
      return node is not None and node.isWord


    def startsWith(self, prefix: str) -> bool:
      return self.searchPrefix(prefix) is not None

class TrieNode:
    def __init__(self):
        self.children = {}
        self.isWord = False

# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

C++

class Trie {
class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    bool isWord;

    TrieNode() {
        isWord = false;
    }
};
private:
  TrieNode* root;

public:
    Trie() {
      root = new TrieNode();
    }

    TrieNode* searchPrefix(string prefix) {
        TrieNode* iter = root;
        for (char letter : prefix) {
            if (iter->children.find(letter) == iter->children.end()) {
                return nullptr;
            }
            iter = iter->children[letter];
        }
        return iter;
    }

    void insert(string word) {
        TrieNode* iter = root;
        for (char letter : word) {
            if (iter->children.find(letter) == iter->children.end()) {
                iter->children[letter] = new TrieNode();
            }
            iter = iter->children[letter];
        }
        iter->isWord = true;
    }

    bool search(string word) {
        TrieNode* node = searchPrefix(word);
        return node != nullptr && node->isWord;
    }

    bool startsWith(string prefix) {
        return searchPrefix(prefix) != nullptr;
    }
};

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

There are two things you have to modify to fit this implementation to any trie problem:

• What additional info will you store (e.g. isWord, word, index).
• Modification on search and insert to adjust to the problem statement. Most of the times you will have far more read queries than writes/building the trie, so extra space and time can be used on the building trie, so we can reduce time on reading/searching queries.