Decode ways

Count the ways to decode a digit string into letters, where A is 1 and Z is 26.

The idea

dp[i] counts the decodings of the first i digits. The last digit used in a decoding is either a single digit 1-9 (add dp[i-1]) or the last two digits form 10-26 (add dp[i-2]). Both can apply at once, so the counts add together.

Code

public static int NumDecodings(string s) {
    var dp = new int[s.Length + 1];
    dp[0] = 1;
    dp[1] = s[0] != '0' ? 1 : 0;
    for (int i = 2; i <= s.Length; i++) {
        if (s[i - 1] != '0') dp[i] += dp[i - 1];
        int two = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
        if (two >= 10 && two <= 26) dp[i] += dp[i - 2];
    }
    return dp[s.Length];
}

Tips

• A leading "0" by itself can never be decoded, since there is no letter for 0.
• "06" is not a valid two-digit code either: only 10 through 26 are.

In the .NET library

A string with a stray 0, like "100", can decode to zero ways even though it looks harmless; "0" only works as the second half of "10" or "20", never alone.