Java DP, O(n) time and O(1) space


  • 21

    The idea for DP is simple when using two helper functions
    ways(i) -> that gives the number of ways of decoding a single character
    and
    ways(i, j) -> that gives the number of ways of decoding the two character string formed by i and j.
    The actual recursion then boils down to :

    f(i) = (ways(i) * f(i+1)) + (ways(i, i+1) * f(i+2))
    

    The solution to a string f(i), where i represents the starting index,

    f(i) = no.of ways to decode the character at i, which is ways(i) + solve for remainder of the string using recursion f(i+1)
    and
    no.of ways to decode the characters at i and i+1, which is ways(i, i+1) + solve for remainder of the string using recursion f(i+2)

    The base case is ,

    return ways(s.charAt(i)) if(i == j) 
    

    The above recursion when implemented with a cache, is a viable DP solution, but it leads to stack overflow error, due to the depth of the recursion. So its better to convert to memoized version.

    For the memoized version, the equation changes to

    f(i) = ( f(i-1) * ways(i) ) + ( f(i-2) *ways(i-1, i) )
    

    This is exactly the same as the previous recursive version in reverse,

    The solution to a string f(i), where i represents the ending index of the string,

    f(i) = solution to the prefix of the string f(i-1) + no.of ways to decode the character at i, which is ways(i)
    and
    solution to the prefix f(i-2) + no.of ways to decode the characters at i - 1 and i, which is ways(i-1, i)

    public class Solution {
        public static int numDecodings(String s) {
            long[] res = new long[2];
            res[0] = ways(s.charAt(0));
            if(s.length() < 2) return (int)res[0];
    
            res[1] = res[0] * ways(s.charAt(1)) + ways(s.charAt(0), s.charAt(1));
            for(int j = 2; j < s.length(); j++) {
                long temp = res[1];
                res[1] = (res[1] * ways(s.charAt(j)) + res[0] * ways(s.charAt(j-1), s.charAt(j))) % 1000000007;
                res[0] = temp;
            }
            return  (int)res[1];
        }
        
        private static int ways(int ch) {
            if(ch == '*') return 9;
            if(ch == '0') return 0;
            return 1;
        }
    
        private static int ways(char ch1, char ch2) {
            String str = "" + ch1 + "" + ch2;
            if(ch1 != '*' && ch2 != '*') {
                if(Integer.parseInt(str) >= 10 && Integer.parseInt(str) <= 26)
                    return 1;
            } else if(ch1 == '*' && ch2 == '*') {
                return 15;
            } else if(ch1 == '*') {
                if(Integer.parseInt(""+ch2) >= 0 && Integer.parseInt(""+ch2) <= 6)
                    return 2;
                else
                    return 1;
            } else {
                if(Integer.parseInt(""+ch1) == 1 ) {
                    return 9;
                } else if(Integer.parseInt(""+ch1) == 2 ) {
                    return 6;
                } 
            }
            return 0;
        }
    }
    

  • 0
    J

    great,so brilliant !


  • 0
    L

    Super smart! Thank you!


  • 1
    J

    Thumb up on the nice way formulating the problem.


  • 0
    Q

    Good Idea. My solution is almost the same with you except "%1000000007", but mine is wrong.

    If remove the code "%1000000007", the result will be wrong. why?

    what's "%1000000007"


  • 0

    @QunWu the problem itself states that
    "since the answer may be very large, you should return the output mod 10^9 + 7." This is just to prevent the integer overflow when the output is v large.


  • 0
    Q

    @johnyrufus16 Oh ya. Thx, i did not see it


  • 0
    T

    Initially I wonder how do you get 15 when both ch1 and ch2 are "*". Then I realize that your ways(i,j) function only consider the case that both characters can be decoded as a whole. So then if the first * represents 1, there are 9 cases (11 12 ... 19); if the first * equals to 2, there are 6 cases (21,22...26)


Log in to reply
 

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