Clean Java Implementation


  • 0
    M

    We can easily replace TrieNode[] with Map<Character, TrieNode> in case we need implement a Trie that supports more than the 26 lower case letters.

    public class Trie {
        private class TrieNode {
            TrieNode[] next = new TrieNode[26];
            boolean isWord = false;
            int cnt = 0;
            public TrieNode(){};
        }
        private TrieNode root;
        public Trie() {
            root = new TrieNode();
        }
        
        /** Inserts a word into the trie. */
        public void insert(String word) {
            if (word == null) return;
            TrieNode cur = root;
            ++cur.cnt;
            for (char c : word.toCharArray()) {
                if (cur.next[c - 'a'] == null) cur.next[c - 'a'] = new TrieNode();
                cur = cur.next[c - 'a'];
                ++cur.cnt;
            }
            cur.isWord = true;
        }
        
        /** Returns if the word is in the trie. */
        public boolean search(String word) {
            if (word == null) return false;
            TrieNode cur = root;
            for (char c : word.toCharArray()) {
                if (cur.next[c - 'a'] == null) return false;
                cur = cur.next[c - 'a'];
            }
            return cur.isWord;
        }
        
        /** Returns if there is any word in the trie that starts with the given prefix. */
        public boolean startsWith(String prefix) {
            if (prefix == null) return false;
            TrieNode cur = root;
            for (char c : prefix.toCharArray()) {
                if (cur.next[c - 'a'] == null) return false;
                cur = cur.next[c - 'a'];
            }
            return cur.cnt > 0;
        }
    }
    

Log in to reply
 

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