Java solution that uses the fibbonati sequence


  • 0
    V

    This solution will go through the string locating "bifurcation" positions, where the sequence can be interpreted in more than a single form. For instance on "87651234" the substring "123" is a bifurcation that can be decoded in 3 different ways ("1,2,3", "12,3", "1,23").

    Once I have this I just have to figure out all the possible ways a string of length (n) can be decoded. This grows like a Fibonacci sequence that start with 1 and 2, or 2 and 3 depending on how you interpret the "size" here. Just check the rough visual aid to see why. The image uses an imaginary input that is all "1".

    0_1481758265447_Screenshot from 2016-12-14 15-30-13.png

    From the image you can see that you can reach the next level by repeating the current level pre-pending "1," and the previous one pre-pending "11,".

    enum State {
        EMPTY,
        ONE,
        TWO
    };
    
    /**
     * @param s a string,  encoded message
     * @return an integer, the number of ways decoding
     */
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
    
        State state = State.EMPTY;
        int total = 1;
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c < '0' || c > '9') {
                throw new RuntimeException("unexpected '" + c + "'");
            }
    
            switch(state) {
                case EMPTY:
                    if (c == '0') {
                        return 0;
                    }
                    break;
                case ONE:
                    if (c != '0') {
                        count++;
                    } else {
                        count--;
                    }
                    break;
                case TWO:
                    if (c > '0' && c <= '6' ) {
                        count++;
                    }
                    if (c == '0') {
                        count--;
                    }
                    break;
            }
            if (c == '1') {
                state = State.ONE;
            } else if (c == '2') {
                state = State.TWO;
            } else {
                total *= fib(count);
                count = 0;
                state = State.EMPTY;
            }
        }
        return total * fib(count);
    }
    
    static ArrayList<Integer> fibCache = new ArrayList<>();
    static {
        fibCache.add(1);
        fibCache.add(2);
        fibCache.add(3);
    }
    int fib(int count) {
        if (count < 0) {
            return 1;
        }
        while (count > fibCache.size() - 1) {
            int size = fibCache.size();
            fibCache.add(fibCache.get(size -1) + fibCache.get(size -2));
        }
        return fibCache.get(count);
    }
    

    This particular implementation uses a state machine to keep a count of the size of the bifurcation local.

    The fibbonati function is doing memoisation to speed up the O(n) fib calculation.

    Some possible optimizations would be to search for specific bifurcation points and count them.


Log in to reply
 

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