Share my JAVA dp solution


  • 0
    W


    public class Solution {
    private final int DIV = 1000000007;

    public int numDecodings(String s) {
        if (s.length() == 0){
            return 0;
        }
        if (s.length() == 1){
            return (int)getPossibleDecodeWays(s.charAt(0));
        }
        int len = s.length();
        long dp[] = new long[len];
        dp[len-1] = getPossibleDecodeWays(s.charAt(len-1));
        dp[len-2] = getPossibleDecodeWays(s.charAt(len-2))*dp[len-1] + getPossibleDecodeWays(s.substring(len-2));
        for (int i = len-3; i >= 0; i--){
            dp[i] = getPossibleDecodeWays(s.charAt(i))*dp[i+1]%DIV + getPossibleDecodeWays(s.substring(i,i+2))*dp[i+2]%DIV;
            dp[i] %= DIV;
        }
        return (int)dp[0];
    }
    

    //get getPossibleDecodeWays for substring which length == 1
    private long getPossibleDecodeWays(char c){
    if (c == '0'){
    return 0;
    }
    else if (c == '*'){
    return 9;
    }
    else{
    return 1;
    }
    }

    //get getPossibleDecodeWays for substring which length == 2
    private long getPossibleDecodeWays(String s){
        if (s.charAt(0) == '0'){
            return 0;
        }
        else if (s.equals("**")){
            return 15;
        }
        else if (s.charAt(0) == '*'){
            //*&digit
            if (s.charAt(1) >= '0' && s.charAt(1) <= '6'){
                return 2;
            }
            else{
                return 1;
            }
        }
        else if (s.charAt(1) == '*'){
            //digit&*
            if (s.charAt(0) == '1'){
                return 9;
            }
            else if (s.charAt(0) == '2'){
                return 6;
            }
            else{
                return 0;
            }
        }
        else{
            //digit&digit
            return (s.charAt(0)-'0')*10 + (s.charAt(1)-'0') <= 26? 1: 0; 
        }
    }
    

    }


  • 0
    W

    @wenjiaxie There is something wrong with the format


Log in to reply
 

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