Implement a trie with insert, search, and startsWith methods.
Note: You may assume that all inputs are consist of lowercase letters a-z.
Subscribe to see which companies asked this question.
Solution:
Tips:
Trie tree
Java Code:
public class Trie { private TrieNode[] head; /** Initialize your data structure here. */ public Trie() { head = new TrieNode[256]; } /** Inserts a word into the trie. */ public void insert(String word) { TrieNode[] tail = head; TrieNode node = null; for (int i = 0; i < word.length(); i++) { char c = word.charAt(i); node = tail[c]; if (node == null) { node = new TrieNode(c); tail[c] = node; } tail = node.next; } node.endFlg = true; } /** Returns if the word is in the trie. */ public boolean search(String word) { TrieNode[] p = head; int i = 0; TrieNode node = null; for (; i < word.length(); i++) { char c = word.charAt(i); node = p[c]; if (null == node || node.c != c) { break; } p = p[c].next; } return i == word.length() && node.endFlg; } /** Returns if there is any word in the trie that starts with the given prefix. */ public boolean startsWith(String prefix) { TrieNode[] p = head; int i = 0; for (; i < prefix.length(); i++) { char c = prefix.charAt(i); if (p[c] == null || p[c].c != c) { break; } p = p[c].next; } return i == prefix.length(); } public static class TrieNode { public TrieNode(char c) { this.c = c; } public char c; public boolean endFlg = false; public TrieNode[] next = new TrieNode[256]; } } /** * 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); */