C# - DP with explanation how to handle the zero


  • 0

    handling the zero is the tricky part of this solution. Beside that there is a dp pattern. When you can make a 2 digit number you sum the previous 2 answers, else you carry forward just the previous answer. The zero requires that you make a 2 digit number and you carry forward the answer from 2 back (not previous, rather previous previous). If you cannot pair the zero to make a 2 digit number then your sequence is invalid and return 0. You will notice you don't need the array, you could just track previous 2 values with ints.

        public int NumDecodings(string s) 
        {
            if (s.Length == 0 || s[0] == '0') return 0;
            
            int[] dp = new int[s.Length+1];
            dp[0] = 1;
            dp[1] = 1;
            for (int i = 1; i < s.Length; i++)
            {
                if (s[i] == '0')
                {
                    if (s[i-1] != '1' && s[i-1] != '2') return 0;
                    dp[i+1] = dp[i-1];
                }
                else if (s[i-1] == '1' || (s[i-1] == '2' && s[i] - '0' <= 6))
                {
                    dp[i+1] = dp[i] + dp[i-1];
                }
                else
                {
                    dp[i+1] = dp[i];
                }
            }
            
            return dp[s.Length];
        }
    

Log in to reply
 

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