Java Solution: Use only one Integer array


  • 0
    S

    Something like DoubleArrayTrie,but more simple with losing some space efficiency. The core idea is when I need to create a trie node,I don't really create one, I generate a base using the array's maxSize and enlarge the array by 26 to hold the new one node's children.

    public class Trie {
        /**
         * In base,0 means null,positive means a path,negative means a word
         */
        Arr base=new Arr();
    
        public Trie() {
            /**
             * allocate space for the root and root's children
             */
            base.set(0,1);
            base.setSize(1+26);
        }
    
        public void insert(String word) {
            int currentState=0;
            for (char c : word.toCharArray()) {
                int currentBase=Math.abs(base.get(currentState));
                int nextState=currentBase+getOffset(c);
                if (base.get(nextState)==0){
                    int nextBase=base.size();
                    base.set(nextState,nextBase);
                    base.setSize(base.size()+26);
                }
                currentState=nextState;
            }
            base.set(currentState,-1*Math.abs(base.get(currentState)));
        }
    
    
        public boolean search(String word) {
            int currentState=0;
            for (char c : word.toCharArray()) {
                int currentBase=Math.abs(base.get(currentState));
                int nextState=currentBase+getOffset(c);
                if (base.get(nextState)==0)
                    return false;
                currentState=nextState;
            }
            return base.get(currentState)<0;
        }
    
        public boolean startsWith(String prefix){
            int currentState=0;
            for (char c : prefix.toCharArray()) {
                int currentBase=Math.abs(base.get(currentState));
                int nextState=currentBase+getOffset(c);
                if (base.get(nextState)==0)
                    return false;
                currentState=nextState;
            }
            return true;
    
        }
    
        /*
        a-z -> 0~25
         */
        private int getOffset(char c){
            return c-'a';
        }
    
        private static class Arr {
            private int[] a;
            private int size;
    
            public Arr() {
                a = new int[10];
            }
    
            public void set(int idx, int value) {
                if (idx > a.length - 1) {
                    resize(idx);
                }
                a[idx] = value;
                if (idx + 1 > size)
                    size = idx + 1;
            }
    
            public int get(int idx) {
                if (idx > a.length - 1)
                    return 0;
                return a[idx];
            }
    
            public int size() {
                return size;
            }
    
            public void setSize(int size){
                this.size=size;
            }
    
    
            private void resize(int idx) {
                int len = a.length;
                int newLen = Math.max(len * 2, idx + 1);
                a = Arrays.copyOf(a, newLen);
            }
        }
    
    }
    

Log in to reply
 

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