C# O(n) DP solution (Beats 90%)


  • 0
    K

    I use a DP array such that dp[i] is the number of decodings for a string of length i - 1. The reason the DP needs to be one index longer than the length is just incase the first decoding path consumes 2 letters. Either way, whether it consumes 1 letter or 2 letters, initially, the number of decodings starts at 1. If the current character I'm analyzing in the loop is not a 0 (can be consumed as 1 letter), I can simply take the number of previous decodings. If the current character can also be consumed as 2 letters, I can take the second previous decoding sum.

        public int NumDecodings(string s)
        {
            if(string.IsNullOrEmpty(s) || s[0] == '0'){
                return 0;
            }
            
            int n = s.Length;
            int[] dp = new int[n+1];
            dp[0] = 1;
            dp[1] = 1;
            
            for(int i = 2; i <= n; ++i){
                int first = (int)Char.GetNumericValue(s[i - 1]);
                int second = (int)Convert.ToInt32(s.Substring(i - 2, 2));
                if(first != 0) {
                    dp[i] += dp[i-1];  
                }
                if(second >= 10 && second <= 26) {
                    dp[i] += dp[i-2];
                }
            }
            
            return dp[n];
        }

Log in to reply
 

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