A 9-Line DP Solution by calculating adjacent 2 digits with explanations


  • 1
    L

    To play around char "0", I am calculating the adjacent 2 digits s[i-1]
    and s[i] to make it a 2-digit number codeInt. codeInt has a few cases

    1. codeInt == 0 : This is case of "0###" need return 0
    2. codeInt == 30/40/50...: This is case of "##80###" need return 0
    3. codeInt == 10/20 : This is the case of "###10####" or "####20###", which won't increase Decoding numbers, and equal to the decoding number of [i-2] (dp1 = dp2)
    4. 10 < codeInt <= 26 : These are the cases without 0, and increase Decoding numbers (dp1 += dp2)
    5. codeInt > 26 : These are the cases without 0, and won't increase Decoding numbers (dp1 = dp1)
    public int NumDecodings(string s) {
        int dp1 = 1, dp2 = 1;
        for(int i = 0; i < s.Length; i++){
            int codeInt = 10 * (i == 0 ? 0 : s[i - 1] - '0') + s[i] - '0', tmp = dp1;
            if(s[i] == '0' && (codeInt == 0 || codeInt > 20)) return 0;
            if (codeInt == 10 || codeInt == 20) dp1 = dp2;
            else if (10 < codeInt && codeInt <= 26) dp1 += dp2;
            dp2 = tmp;
        }
        return s.Length == 0 ? 0 : dp1; }

Log in to reply
 

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