Start learning free

LESSON 450 OF 540 · DYNAMIC PROGRAMMING

Decode Ways in TypeScript: O(n) Dynamic Programming

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

    TYPESCRIPT · DYNAMIC PROGRAMMING

    Decode Ways in TypeScript, explained

    Problem overview

    numDecodings receives a string s of digits and returns how many ways it can be read as a message of capital letters, where A is 1, B is 2, up to Z as 26. Decoding means splitting the digits into groups, each a number from 1 to 26, and turning each group into its letter. A group can't start with 0: no letter is 0, and "06" is not the same as "6". If no split works, the answer is 0.

    For "12" the answer is 2: 1, 2 gives "AB" and 12 gives "L". For "226" it is 3: 2, 26, 22, 6 and 2, 2, 6. For "06" it is 0, because the first group would have to start with 0.

    The statement asks for O(n) time, where n is the length of s.

    Approach: count decodings of each beginning

    Trying every split directly would explore a tree of choices that doubles at almost every digit. The better view is to count the decodings of each beginning of the string and build longer beginnings from shorter ones.

    Let dp[i] be the number of ways to decode the first i digits. Consider how a decoding of those i digits can end. Its last group is either one digit or two:

    • One digit, s[i - 1]. It is a letter if it isn't '0'. Every decoding of the first i - 1 digits, followed by this letter, is a decoding of the first i digits. That adds dp[i - 1].
    • Two digits, s[i - 2] and s[i - 1]. They form a letter if their value is between 10 and 26. A pair like 07 starts with 0 and is not allowed, and 27 or more is not a letter. That adds dp[i - 2].

    These two cases never produce the same decoding, so dp[i] is their sum. Each entry takes constant work, which gives O(n) overall.

    Step by step

    1. The length. Store s.length in const n.
    2. The table. dp is a number[] of n + 1 zeros, created with new Array(n + 1).fill(0). It has one more entry than there are digits, because dp[0] stands for the empty beginning.
    3. The empty beginning. Set dp[0] = 1. The empty string has exactly one decoding, the empty message, and every longer decoding builds on it, so it must count as one.
    4. The first digit. If s[0] !== '0', set dp[1] = 1. A single digit from 1 to 9 is one letter. If the string starts with 0, dp[1] stays 0, and so does everything built on it.
    5. The loop. i goes from 2 to n inclusive, because the first two entries are already known and the last one, dp[n], covers all of s.
    6. One-digit ending. If s[i - 1] !== '0', add dp[i - 1] to dp[i] with +=.
    7. Read the pair. s.substring(i - 2, i) holds the characters at positions i - 2 and i - 1. Convert it with Number into const two.
    8. Two-digit ending. If two >= 10 && two <= 26, add dp[i - 2] to dp[i].
    9. Answer. Return dp[n].

    The solution in TypeScript

    class Solution {
    numDecodings(s: string): number {
        const n = s.length;
        const dp: number[] = new Array(n + 1).fill(0);
        dp[0] = 1;
        if (s[0] !== '0') {
            dp[1] = 1;
        }
        for (let i = 2; i <= n; i++) {
            if (s[i - 1] !== '0') {
                dp[i] += dp[i - 1];
            }
            const two = Number(s.substring(i - 2, i));
            if (two >= 10 && two <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }
}

    TypeScript details

    • new Array(n + 1).fill(0) creates an array of n + 1 slots and fills each with 0. The annotation number[] tells the compiler what the array holds; it disappears when the code compiles to JavaScript.
    • const dp means the variable always refers to the same array. The entries inside can still change, which is what dp[i] += ... does.
    • s[i - 1] is a one-character string, so it is compared with the string '0', not the number 0. With !== a number and a string are never equal.
    • Number("07") is 7, so the range check two >= 10 is what rejects pairs that start with 0. Number("26") is 26.
    • number is a double. Counts stay exact up to 2^53, and the statement guarantees the answer fits in 32 bits.

    Tracing examples

    Printing the table the solution builds gives these values:

    sdpAnswer
    "226"[1, 1, 2, 3]3
    "11106"[1, 1, 2, 3, 2, 2]2
    "100"[1, 1, 1, 0]0

    In "226", dp[2] is 2: the digit 2 on its own after "2" gives one way, and the pair 22 gives another. dp[3] adds dp[2] for the 6 alone and dp[1] for the pair 26, which is 2 + 1 = 3.

    In "100", the second 0 can't stand alone, and 00 is no letter, so dp[3] is 0. In "11106", the 0 can only pair with the 1 before it as 10, which is why the count drops from 3 to 2 at that point and stays 2 after the 6.

    Complexity

    Time: O(n). The loop runs n - 1 times with a constant amount of work each.

    Space: O(n) for the table. Each entry only needs the two before it, so two variables would be enough, but the table keeps the code easy to follow.

    Edge cases and common mistakes

    • Strings that start with 0. "06" returns 0, and so does "0". dp[1] stays 0, and the pair 06 is rejected because 6 is below 10.
    • A 0 that can't be paired. "30" and "100" return 0: 30 is above 26 and 00 is not a letter, so the 0 has nowhere to go. "10" returns 1, since 10 is the letter J.
    • Pairs above 26. "27" returns 1: only 2 and 7 separately.
    • One digit. "1" and "9" return 1. The loop doesn't run, and dp[1], set before it, is returned.
    • Forgetting dp[0] = 1. Every two-digit case reaches back to dp[0] when the pair is at the very start, so with 0 there "12" would give 1 instead of 2.
    • Accepting a leading zero in a pair. Without the two >= 10 test, 07 would pass as 7.

    Testing

    Running numDecodings on small inputs gives:

    sResult
    "12"2
    "226"3
    "06"0
    "11106"2
    "10"1
    "0"0
    "27"1
    "30"0
    "100"0
    "2101"1
    "1"1
    Keep going with TypeScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free