Start learning free

LESSON 449 OF 539 · DYNAMIC PROGRAMMING

Decode Ways in C#: Dynamic Programming over the Digits in O(n)

Practice O(n) Read the full explanation

A message made of the capital letters A to Z was turned into digits by writing each letter as its position in the alphabet: A becomes 1, B becomes 2, and so on up to Z, which becomes 26.

To decode the digits, split them into groups, each group a number from 1 to 26, and turn each group back into its letter. A group can't start with 0: "06" is not the same as "6", and no letter is 0. For example, "11106" can be decoded in two ways:

  • "AAJF", from the groups 1, 1, 10, 6;
  • "KJF", from the groups 11, 10, 6.

The groups 1, 11, 06 don't work, because 06 starts with 0.

Given a string s of digits, return the number of ways to decode it. If it can't be decoded at all, return 0.

Example 1:

Input: s = "12"
Output: 2
Explanation: "12" can be decoded as "AB" (1, 2) or as "L" (12).

Example 2:

Input: s = "226"
Output: 3
Explanation: "226" can be decoded as "BZ" (2, 26), "VF" (22, 6) or "BBF" (2, 2, 6).

Example 3:

Input: s = "06"
Output: 0
Explanation: The first group would have to start with 0: "0" is no letter, and "06" can't be read as 6. So "06" can't be decoded.

Constraints:

  • 1 <= s.length <= 100
  • s is made of digits only, 0 to 9, and may start with 0.
  • The answer fits in a 32-bit integer.

Note:

Your algorithm should run in O(n) time, where n is the length of s.

STEP 1 OF 9
    Ctrl + Enter to check

    C# · DYNAMIC PROGRAMMING

    Decode Ways in C#, explained

    Problem overview

    NumDecodings receives a string s of digits and returns how many ways it can be read as letters, where A is 1, B is 2, and so on up to Z as 26. A reading splits the digits into groups, each a number from 1 to 26, and no group may start with 0: "06" is not 6, and no letter is 0. If there is no valid reading, the answer is 0.

    For "12" the answer is 2: AB (1, 2) or L (12). For "226" it is 3: BZ (2, 26), VF (22, 6) or BBF (2, 2, 6). For "06" it is 0, since the first group would have to start with 0.

    Approach: count the readings of each beginning

    Let dp[i] be the number of ways to decode the first i digits of s. The last group of a reading of those i digits is either one digit or two digits, and nothing else:

    • If the last digit alone is a letter (it is not '0'), then every reading of the first i - 1 digits can be extended by that letter. That adds dp[i - 1] ways.
    • If the last two digits form a number from 10 to 26, they are one letter, and every reading of the first i - 2 digits can be extended by it. That adds dp[i - 2] ways.

    The two cases never produce the same reading, because the last group has a different length. So dp[i] is the sum of the cases that apply, and each entry takes constant work: O(n) time overall. A plain recursion that tries both group sizes at each position repeats the same suffixes many times; the table computes each one once.

    Step by step

    1. Store the length: int n = s.Length.
    2. Create the table: int[] dp = new int[n + 1]. It has one more entry than there are digits, because dp[0] stands for the empty beginning. C# fills a new int array with zeros.
    3. dp[0] = 1. The empty beginning has exactly one decoding, the empty message. Every longer decoding is built on it, so it counts as one way, not zero.
    4. First digit: if s[0] != '0', set dp[1] = 1. A single digit 1 to 9 is a letter. If the string starts with 0, dp[1] stays 0, and every count built on it stays 0 as well.
    5. Loop i from 2 while i <= n. The entries 0 and 1 are known, and the last one, dp[n], covers all of s.
    6. One-digit group: if s[i - 1] != '0', do dp[i] += dp[i - 1].
    7. Two-digit group: take s.Substring(i - 2, 2), turn it into an int with int.Parse, and keep it in two.
    8. Valid pair: if two >= 10 && two <= 26, do dp[i] += dp[i - 2]. A pair like 07 parses to 7 and is rejected because it is below 10; a pair above 26 is no letter either.
    9. Return dp[n].

    The solution in C#

    class Solution {
    public int NumDecodings(string s) {
        int n = s.Length;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        if (s[0] != '0') {
            dp[1] = 1;
        }
        for (int i = 2; i <= n; i++) {
            if (s[i - 1] != '0') {
                dp[i] += dp[i - 1];
            }
            int two = int.Parse(s.Substring(i - 2, 2));
            if (two >= 10 && two <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }
}

    C# details worth knowing:

    • s[i] is a char, compared with a character literal in single quotes: s[0] != '0'. Comparing it with the string "0" would not compile. A char is not the number it shows: s[0] - '0' gives the digit's value as an int, while (int)s[0] would give the character code, 48 for '0'.
    • Substring(start, length) takes a start index and a length, not an end index: "226".Substring(1, 2) is "26". The second argument is how many characters to take.
    • int.Parse accepts leading zeros: int.Parse("07") is 7. That is why the range check starts at 10, which excludes pairs that begin with 0. The input contains only digits, so Parse never throws here.
    • Strings are immutable. Substring creates a new string each time it is called, and nothing changes in s. That small allocation per position is what the two-digit step costs; computing (s[i - 2] - '0') * 10 + (s[i - 1] - '0') avoids it.
    • += on an array element works like on any variable: dp[i] += dp[i - 1] adds to the entry in place.
    • The result is an int. The lesson guarantees the answer fits in 32 bits. In general, int overflow wraps silently, so a longer string could give a wrong number; long would be needed for larger answers.

    Complexity

    Time: O(n). The loop runs n - 1 times and does constant work per step: one comparison, one parse of two characters and at most two additions.

    Space: O(n) for the dp table. Each entry needs only the two before it, so two variables could replace the table and reduce the space to O(1).

    Edge cases and common mistakes

    • A leading zero. "06" returns 0 and "0" returns 0.
    • A zero that can't be paired. "100" returns 0: the last 0 would have to join the previous 0 as 00, which is no letter. And "30" returns 0, because 30 is above 26 and the 0 can't stand alone.
    • A zero that can be paired. "10" returns 1, only J. The one-digit step is skipped for the 0, and the two-digit step adds dp[0].
    • Numbers just above 26. "27" returns 1 (only 2 and 7), because 27 is not a letter.
    • One digit. "1" returns 1. For n = 1 the loop doesn't run, and the code relies on dp[1] having been set before it.
    • Forgetting dp[0] = 1. Every two-digit case would add 0 where it should add 1, and "12" would give 1 instead of 2.
    • Accepting "07" as 7. That mistake comes from checking only two <= 26. The lower bound of 10 is what rules it out.

    Testing

    Running NumDecodings and printing the dp table next to each result gives:

    s = "12"     dp = 1 1 2         -> 2
s = "226"    dp = 1 1 2 3       -> 3
s = "06"     dp = 1 0 0         -> 0
s = "11106"  dp = 1 1 2 3 2 2   -> 2
s = "10"     dp = 1 1 1         -> 1
s = "27"     dp = 1 1 1         -> 1
s = "100"    dp = 1 1 1 0       -> 0
s = "30"     dp = 1 1 0         -> 0
s = "2101"   dp = 1 1 2 1 1     -> 1

    In the table for "226", dp[2] is 2 because "22" reads as 2, 2 or as 22. For dp[3], the last digit 6 is a letter on its own and adds dp[2], which is 2. The pair "26" is also a letter and adds dp[1], which is 1. Together: 2 + 1 = 3.

    Keep going with C#500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free