Start learning free

LESSON 446 OF 536 · DYNAMIC PROGRAMMING

Decode Ways in Java: 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

    JAVA · DYNAMIC PROGRAMMING

    Decode Ways in Java, explained

    Problem overview

    A message of capital letters was turned into digits by writing each letter as its position in the alphabet: 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 back into a letter. A group can't start with 0: "06" is not 6, and no letter is 0.

    The method numDecodings receives the digit string s and returns how many ways it can be decoded, or 0 if there are none. 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, because the first group would have to start with 0.

    Approach: count decodings of every beginning

    Look at the last group of a decoding of the first i digits. It is either the last digit alone (a letter if that digit is 1 to 9), or the last two digits together (a letter if they form a number from 10 to 26). Whatever comes before that group is a decoding of the first i - 1 or i - 2 digits. So the number of ways to decode the first i digits is

    • the ways for the first i - 1 digits, if the last digit isn't 0, plus
    • the ways for the first i - 2 digits, if the last two digits form a number from 10 to 26.

    That is a table dp with dp[i] as the number of ways to decode the first i digits. Each entry needs only the two before it and a constant amount of work, so the table is filled in O(n) time. Trying every split by recursion without the table repeats the same suffixes many times and is exponential in the worst case.

    The table starts with dp[0] = 1: the empty beginning has exactly one decoding, with no letters. Every longer decoding is built on it, so it has to count as one way, not zero.

    Step by step

    1. Store the length of s in n.
    2. Create dp as an int[] of size n + 1, one more than the digits, because dp[0] stands for the empty beginning. Java fills a new int array with zeros.
    3. Set dp[0] to 1.
    4. Set dp[1]. If the first character isn't '0', one digit alone is a letter, so dp[1] is 1. If it is '0', dp[1] stays 0, and every count built on it does too.
    5. Loop with i from 2 up to and including n. The first two entries are known, and the last one, dp[n], covers all of s.
    6. The last digit alone. If s.charAt(i - 1) isn't '0', add dp[i - 1] to dp[i].
    7. Read the last two digits as a number: Integer.parseInt(s.substring(i - 2, i)), stored in two.
    8. The last two digits together. If two is from 10 to 26, add dp[i - 2] to dp[i]. A pair below 10, such as 07, starts with 0 and is no letter, and neither is 27 or more.
    9. Return dp[n].

    Here is the table for "226", from a real run of the solution's loop:

    dp = [1, 1, 2, 3]

    Entry 1 is 1 (the digit 2). Entry 2 is 2: the digit 2 on its own adds dp[1], and the pair 22 adds dp[0]. Entry 3 is 3: the digit 6 on its own adds dp[2] = 2, and the pair 26 adds dp[1] = 1. For "11106" the table is

    dp = [1, 1, 2, 3, 2, 2]

    and the answer is 2, matching AAJF and KJF.

    The solution in Java

    class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        int[] dp = new int[n + 1];
        dp[0] = 1;
        if (s.charAt(0) != '0') {
            dp[1] = 1;
        }
        for (int i = 2; i <= n; i++) {
            if (s.charAt(i - 1) != '0') {
                dp[i] += dp[i - 1];
            }
            int two = Integer.parseInt(s.substring(i - 2, i));
            if (two >= 10 && two <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }
}

    Java details worth a closer look:

    • charAt and char comparison. s.charAt(i - 1) returns a char, and != '0' compares it with the character zero. Single quotes make a char; "0" with double quotes would be a String.
    • substring(i - 2, i) takes the characters at positions i - 2 and i - 1: the end index is excluded.
    • Integer.parseInt and leading zeros. It accepts them: Integer.parseInt("07") is 7. That is why the code checks the range 10 to 26 and not just "at most 26": 7 is below 10, so the pair 07 is rejected.
    • += on an array element. dp[i] += dp[i - 1] adds to the entry in place. Both branches can fire for the same i, and then the entry is the sum of the two.
    • int overflow. Counts can grow like Fibonacci numbers, and an int wraps silently when it overflows. The lesson promises that the answer fits in 32 bits, so int is enough here. With 45 ones, "111...1", the answer is 1836311903, close to the limit of 2147483647.

    Complexity

    Time: O(n). The loop runs n - 1 times, and each pass does a constant amount of work: two character checks, one short substring and one parseInt.

    Space: O(n) for the table. Each entry depends only on the two before it, so two variables would be enough, but the table makes the idea easier to follow.

    Edge cases and common mistakes

    • A leading zero. "06" gives 0: dp[1] stays 0, the last digit 6 adds dp[1] = 0, and the pair 06 is 6, which is below 10, so nothing is added.
    • Zeros in the middle. "10" gives 1, only J, because the 0 can't stand alone and the pair 10 is a letter. "100" gives 0: the pair 10 is a letter but leaves the last 0 alone, and the pair 00 is not a letter. "30" and "60" also give 0, since 30 and 60 are above 26. "101" gives 1, only JA.
    • Pairs above 26. "27" gives 1, only BG: the pair 27 is not a letter.
    • One digit. "1" gives 1 and "0" gives 0. The loop doesn't run, and dp[1] is the answer. This is why the table has n + 1 entries even for n == 1.
    • Treating dp[0] as 0. Every count would be 0. The empty beginning is one way to decode nothing.
    • Checking only two <= 26. That lets 07 and 00 through. The lower bound of 10 is what rules out a group that starts with 0.
    • An empty string. The lesson's strings have at least one character. For an empty string, s.charAt(0) throws StringIndexOutOfBoundsException.

    Testing

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