More flexible solution with ArrayList in java.


  • 0
    D

    In my solution, I did not initialize an array of TrieNode[26]. Instead, I just use a ArrayList structure in TrieNode and add a character when needed. I think it's more flexible than the common solution and not limited to 26 alphabets.

    Here is the code:

    import java.util.ArrayList;
    
    public class Trie {
        private TrieNode root;
     
        /** Initialize your data structure here. */
        public Trie() {
            root = new TrieNode();        
        }
        
        /** Inserts a word into the trie. */
        public void insert(String word) {
            TrieNode rootNode = root;
            char[] wChars = word.toCharArray();
            for (char c : wChars) {
                if (rootNode.getChildren(c) == null) {
                    rootNode.addChildren(c);
                }
                rootNode = rootNode.getChildren(c);
            }
            rootNode.isWord = true;
        }
        
        /** Returns if the word is in the trie. */
        public boolean search(String word) {
            TrieNode rootNode = root;
            char[] wChars = word.toCharArray();
            for (char c : wChars) {
                if (rootNode.getChildren(c) == null) {
                    return false;
                }
                rootNode = rootNode.getChildren(c);
            }
            return rootNode.isWord;
        }
        
        /** Returns if there is any word in the trie that starts with the given prefix. */
        public boolean startsWith(String prefix) {
            TrieNode rootNode = root;
            char[] wChars = prefix.toCharArray();
            for (char c : wChars) {
                if (rootNode.getChildren(c) == null) {
                    return false;
                }
                rootNode = rootNode.getChildren(c);
            }
            return true;        
        }
        
        class TrieNode {
            private char val;
            private boolean isWord;
            private ArrayList<TrieNode> children = new ArrayList<>();
            
            public TrieNode() {
                this(' ');
            }
            public TrieNode(char w) {
                this.val = w;
                this.isWord = false;
                this.children = new ArrayList<>();
            }
            public TrieNode getChildren(char w) {
                for (TrieNode node : this.children) {
                    if (node.val == w) {
                        return node;
                    }
                }
                return null;
            }
            public void addChildren(char w) {
                children.add(new TrieNode(w));
            }
        }
    }
    

Log in to reply
 

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