Cfrtjryk

I'm working on problem 91 on Leetcode.com called "Decode Ways" and I've successfully managed to get a working recursive solution but it results in Time Limited Exceeded (TLE). I'm new to utilizing memoization and I've been unable to discover how to properly memoize my results at each recursive step and check if I've already solve the sub-problem.

Prompt:

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1 'B' -> 2 ... 'Z' -> 26

Given a non-empty string containing only digits, determine the total
number of ways to decode it.

Working Code (TLE):

public int NumDecodings(string s) 

{

    if (s == null || s.Length == 0) return 0;

    // int dp = new int[s.Length + 1];

    // for (int i = 0; i < dp.Length; ++i) dp[i] = -1;

    // dp[0] = 1;

    // dp[1] = Decode(s, 0, 1, dp) + Decode(s, 0, 2, dp);

    int jump1 = Decode(s, 0, 1);

    int jump2 = Decode(s, 0, 2);

    return jump1 + jump2;

    // return dp[1];

}



public int Decode(string s, int i, int len)

{

    if (i + len - 1 >= s.Length)

        return 0;



    // if (dp[i] > -1)

    //     return dp[i];



    int sub = Convert.ToInt32(s.Substring(i, len));

    if (sub > 26 || sub < 1 || s.Substring(i, len)[0] == '0') 

        return 0;

    else if (i + len - 1 == s.Length - 1 && sub < 27 && sub > 0)

        return 1;



    int jump1 = i + len - 1 + 1 < s.Length ? Decode(s, i + len, 1) : 0;

    int jump2 = i + len - 1 + 2 < s.Length ? Decode(s, i + len, 2) : 0;

    // dp[i] = jump1 + jump2;



    return jump1 + jump2;

    // return dp[i];

}

Memoization

Looking into memoization is a good idea - in this case it allows you to achieve $O(n)$ runtime performance instead of $O(n^2)$. One way to add memoization is to create a wrapper method that takes the same arguments as Decode. This method first looks up the given arguments in a dictionary, and if they're present, it can return the memoized result. If not, it will call Decode and store its result in the dictionary before returning it.

However, I would recommend removing NumDecodings and rewriting Decode so it only takes a single string parameter. That will simplify memoization and make it a little more efficient. For example, "412123" and "512123" both have the same suffix ("12123"), but because the 'sub-calls' ("412123", 1, 1) and ("512123", 1, 1) use different arguments (and thus different memoization keys) you won't benefit from memoization across those different inputs.

Other notes

• Instead of passing the original input string and an offset and length, consider passing 'the rest of the string' instead. Decode can then call Decode(s.Substring(1)) if the leading digit is a valid unit, and Decode(s.Substring(2)) if the leading 2 digits are a valid unit.


• There are various things in the current code that can be simplified:
  
  
  
  
  • 
    if (i + len - 1 >= s.Length) to if (i + len > s.Length)
    
  
  
  • 
    s.Substring(i, len)[0] == '0' to s[i] == '0'
    
  
  
  • 
    else if (i + len - 1 == s.Length - 1 to else if (i + len == s.Length
    
  
  
  • 
    jump1 = i + len - 1 + 1 to jump1 = i + len
    
  
  
  • 
    jump2 = i + len - 1 + 2 to jump2 = i + len + 1
    
  
  
  
  


• Moving s.Substring(i, len)[0] == '0' to an else if branch allows you to remove the sub < 27 && sub > 0 checks below.


• Disabling code during development is normal, but it's a good idea to clean things up from time to time.


• I would rename Decode to something more descriptive like ValidDecodingsCount - Decode implies that it actually decodes the given input, which is not the case. jump1 and jump2 aren't very descriptive names either, but it's a bit difficult to come up with better names. Maybe rest1Combinations and rest2Combinations?