My solution - optimizing search and prefix function.


  • 0
    M

    Re: AC JAVA solution simple using single array

    My solution - optimizing search and prefix function.

    /** Initialize your data structure here. */
    class TrieNode{
        public TrieNode[] children = new TrieNode[26];
        public boolean endOfWord = false;
        public TrieNode(){};
    }
    private TrieNode root = null;
    public Trie() {
        root = new TrieNode();
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode tmp = root;
        int ind =0;
        for(char ch: word.toCharArray()){
            ind = ch-'a';
            if(tmp.children[ind]==null){
                TrieNode newNode = new TrieNode();
                tmp.children[ind] = newNode;
                tmp = newNode;
            }
            else
                tmp = tmp.children[ind];
        }
        tmp.endOfWord = true;
    }
    
    private boolean iterateWord(String word, boolean isSearch){
        TrieNode tmp = root;
        int ind=0;
        for(char ch: word.toCharArray()){
            ind = ch-'a';
            if(tmp.children[ind]==null) return false;
            tmp = tmp.children[ind];
        }
        return isSearch ? tmp.endOfWord : true;
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        return iterateWord(word, true);
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        return iterateWord(prefix, false);
    }

Log in to reply
 

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