No need to have a TrieNode


  • 0

    public class Trie {
    Trie[] children;
    boolean isWord;

    /** Initialize your data structure here. */
    public Trie() {
        children = new Trie[26];    
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        insert(this, word, 0);
    }
    
    private Trie insert(Trie node, String word, int index) {
        if (node==null) node = new Trie();
        if (index==word.length()) node.isWord=true;
        else {
            int i=word.charAt(index)-'a';
            node.children[i] = insert(node.children[i], word, index+1);
        }
        return node;
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        Trie node = search(this, word, 0);
        return node!=null && node.isWord;
    }
    
    private Trie search(Trie node, String word, int index) {
        if (node==null || word.length()==index) return node;
        int i = word.charAt(index)-'a';
        return search(node.children[i], word, index+1);
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        return search(this, prefix, 0)!=null;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.