208
Implement Trie (Prefix Tree)
24.9%
Medium

class TrieNode {
    // Initialize your data structure here.
    public TrieNode[] childNode;
    public int freq;
    public TrieNode() {
        childNode = new TrieNode[26];
        int freq = 0;
    }
}

public class Trie {
    private TrieNode root;

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

    // Inserts a word into the trie.
    public void insert(String word) {
        insertHelper(word,root);
    }
    private void insertHelper(String word, TrieNode node){
        if (word.length()==0) return;
        int k = word.charAt(0) - 'a';
        if (node.childNode[k] == null) node.childNode[k] = new TrieNode();
        if (word.length() == 1) node.childNode[k].freq++;
        insertHelper(word.substring(1), node.childNode[k]);
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        return searchHelper(word, root);
    }
    private boolean searchHelper(String word, TrieNode node){
        if (word.length()==0){
            if (node.freq>0) return true;
            return false;
        }
        int k = word.charAt(0) - 'a';
        if (node.childNode[k] == null) return false;
        return searchHelper(word.substring(1), node.childNode[k]);
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        return startWithHelper(prefix, root);
    }
    private boolean startWithHelper(String word, TrieNode node){
        if (word.length()==0) return true;
        int k = word.charAt(0) - 'a';
        if (node.childNode[k] == null) return false;
        return startWithHelper(word.substring(1), node.childNode[k]);
    }
}