Neat C# DP Solution


  • 0
    F
        public class Solution {
             public int NumDecodings(string s) {
                 if (String.IsNullOrWhiteSpace(s)) return 0;
                 var cache = new Dictionary <int, int>();
                 // initialize cache at end locations and individual 0s
                 cache[s.Length] = 1;
                 cache[s.Length - 1] = 1;
                 for (int i = 0; i < s.Length; i++)
                 {
                      if (s[i] == '0') cache[i] = 0;
                 }
    
                 return NumDecodingsHelper (s, 0, cache);
            }
    
    public int NumDecodingsHelper(string s, int pos, Dictionary <int, int> cache) {
        if (cache.ContainsKey (pos)) return cache[pos];
        int op = 0;
        var conCatNum = (s[pos] - 0x30) * 10 + (s[pos + 1] - 0x30);
        if (conCatNum > 26) op = NumDecodingsHelper(s, pos + 1, cache);
        else 
        {
            op = NumDecodingsHelper(s, pos + 2, cache) + NumDecodingsHelper(s, pos + 1, cache);
        }
        
        cache[pos] = op;
        
        return op;
    }
    

    }


Log in to reply
 

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