Return to Answer

For small code strings (length < 100) it will help a lot avoiding the creation of the substrings.

For small code strings (length < 100) it will help a lot avoiding the creation of the substrings, but for larger code strings this is a minor problem compared to the bad overall time complexity as Pieter Witvoet has explained.

But if it's about reducing the execution time, I think your major problem is the creation of all those sub strings.

For small code strings (length < 100) it will help a lot avoiding the creation of the substrings.

The below is an iterative version, that to the best of my knowledge is O(n) in time complexity:

public int CountCodeCombinations(string code)
{
  if (string.IsNullOrWhiteSpace(code) || code[0] == '0')
    return 0;

  if (code.Any(ch => !char.IsDigit(ch)))
    throw new ArgumentException("Only digit characters are allowed in the input string", nameof(code));

  int length = code.Length;
  int combinations = 1;
  char current;
  char next;
  int lastCodeIndex = code.Length - 2;
  int lastDifference = 0;

  for (int i = length - 2; i >= 0; i--)
  {
    current = code[i];
    next = code[i + 1];

    if (next == '0')
    {
      if (current > '2' || current == '0')
        return 0;
    }
    else if (current == '1' || current == '2' && next < '7')
    {
      if (i < length - 2 && code[i + 2] == '0')
        continue;

      int oldCombinations = combinations;

      if (combinations == 1)
        combinations += 1;
      else if (lastCodeIndex - i > 1)
        combinations = combinations * 2;
      else
        combinations = combinations * 2 - lastDifference;

      lastDifference = combinations - oldCombinations;
      lastCodeIndex = i;
    }
  }

  return combinations;
}

I'm a little late with this answer, and from your question and the other answers I can't figure out if the problem has changed from TLE to memoization.

But if it's about reducing the execution time, I think your major problem is the creation of all those sub strings.

Below I've refactored your algorithm so it no longer creates strings but instead creates the values to check by looking chars up in the string itself. I've changed the names of your variables - which doesn't improve the execution time but only my understanding of the code :-):

public int NumDecodings(string code)
{
  if (code == null || code.Length == 0) return 0;
  int count1 = Decode(code, 0, 1);
  int count2 = Decode(code, 0, 2);
  return count1 + count2;
}

public int Decode(string code, int offset, int numLength)
{
  if (offset + numLength - 1 >= code.Length || code[offset] == '0')
    return 0;

  int value = 0;

  if (numLength == 1)
    value = code[offset] - '0';
  else
  {
    value = (code[offset] - '0') * 10 + (code[offset + 1] - '0');
  }

  if (value > 26 || value < 1)
    return 0;
  else if (offset + numLength - 1 == code.Length - 1 && value < 27 && value > 0)
    return 1;

  int count1 = offset + numLength - 1 + 1 < code.Length ? Decode(code, offset + numLength, 1) : 0;
  int count2 = offset + numLength - 1 + 2 < code.Length ? Decode(code, offset + numLength, 2) : 0;

  return count1 + count2;
}

When testing against 5000 random valid strings with a max length of 60 the above refactoring reduces the execution time from about 1100 to 60 ms in release mode.

I'm a little late with this answer, and from your question and the other answers I can't figure out if the problem has changed from TLE to memoization.

But if it's about reducing the execution time, I think your major problem is the creation of all those sub strings.

Below I've refactored your algorithm so it no longer creates strings but instead creates the values to check by looking chars up in the code string itself. I've changed the names of your variables - which doesn't improve the execution time but only my understanding of the code :-):

public int NumDecodings(string code)
{
  if (code == null || code.Length == 0) return 0;
  int count1 = Decode(code, 0, 1);
  int count2 = Decode(code, 0, 2);
  return count1 + count2;
}

public int Decode(string code, int offset, int numLength)
{
  if (offset + numLength - 1 >= code.Length || code[offset] == '0')
    return 0;

  int value = 0;

  if (numLength == 1)
    value = code[offset] - '0';
  else
  {
    value = (code[offset] - '0') * 10 + (code[offset + 1] - '0');
  }

  if (value > 26 || value < 1)
    return 0;
  else if (offset + numLength - 1 == code.Length - 1 && value < 27 && value > 0)
    return 1;

  int count1 = offset + numLength - 1 + 1 < code.Length ? Decode(code, offset + numLength, 1) : 0;
  int count2 = offset + numLength - 1 + 2 < code.Length ? Decode(code, offset + numLength, 2) : 0;

  return count1 + count2;
}

When testing against 5000 random valid strings with a max length of 60 the above refactoring reduces the total execution time from about 1100 to 60 ms in release mode.