Short O(n) time O(1) space solution in Java with brief explanantion


  • 0
    M
    /*
        define: ways[i] as number of decoding ways for string s[i:]
        there are only two cases:
        -- initially, at each index i, ways[i] = 0.
        -- if s[i : i + 1] is valid, ways[i] += ways[i + 1]; otherwise ways[i] += 0.
        -- if s[i : i + 2] is valid, ways[i] += ways[i + 2]; otherwise ways[i] += 0.
    */
    public class Solution {
        public int numDecodings(String s) {
            if (s == null || s.length() == 0) return 0;
            int next2 = 1, next1 = 1;  // next2 serves as ways[i + 2]; next1 serves as ways[i + 1]
            for (int i = s.length() - 1; i >= 0; --i) {
                if (next1 == 0 && next2 == 0) return 0;  // an obvious shortcut
                int oneChar = s.charAt(i) >= '1' && s.charAt(i) <= '9' ? 1 : 0;
                int twoChars = i + 1 >= s.length() ? 0 : (s.charAt(i) == '1' && s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '9' || 
                                s.charAt(i) == '2' && s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '6' ? 1 : 0);
                int cur = oneChar * next1 + twoChars * next2;
                next2 = next1;
                next1 = cur;
            }
            return next1;
        }
    }

Log in to reply
 

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