Start learning free

LESSON 453 OF 543 · DYNAMIC PROGRAMMING

Decode Ways in Rust: 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 10
    Ctrl + Enter to check

    RUST · DYNAMIC PROGRAMMING

    Decode Ways in Rust, explained

    Problem overview

    num_decodings 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 decoding splits the digits into groups, each a number from 1 to 26. A group can't start with 0, so "06" is not the letter for 6, and no group is just "0". If no decoding exists, the answer is 0.

    The string "12" has 2 decodings: 1 and 2 (AB), or 12 (L). The string "226" has 3: 2, 26; 22, 6; and 2, 2, 6. The string "06" has none, since the first group would have to start with 0.

    Approach: count the decodings of every beginning

    Let dp[i] be the number of ways to decode the first i digits. The last letter of such a decoding is made of either the last digit alone or the last two digits, so:

    • if digit i (the last of the first i) isn't 0, it can be a letter by itself, and every decoding of the first i - 1 digits extends with it: add dp[i - 1];
    • if the last two digits form a number from 10 to 26, they can be one letter, and every decoding of the first i - 2 digits extends with it: add dp[i - 2].

    The two cases are different groupings, so no decoding is counted twice. A pair such as 07 is below 10, so it is not a letter; 27 and above are too big. Each entry needs only the two before it, so one pass is enough. Trying every grouping recursively would repeat work on the same suffixes; the table remembers it.

    The table needs a starting point. The empty beginning, dp[0], counts as 1 way: no letters. Every longer decoding is built on it. And dp[1] is 1 if the first digit isn't 0, and 0 otherwise.

    Step by step

    1. Take the bytes with s.as_bytes(). A Rust String can't be indexed by position, and each digit is one byte, so bytes[i] is the digit at position i, comparable with b'0', the byte of the character 0.
    2. Store bytes.len() in n. It is a usize, the type of indexes.
    3. Create dp as vec![0i32; n + 1]: one more entry than digits, because dp[0] stands for the empty beginning. The suffix i32 makes the counts match the return type.
    4. Set dp[0] = 1. With 0 here, every count built on it would stay 0.
    5. Set dp[1] = 1 when bytes[0] isn't b'0'. A string starting with 0 can't be decoded, so dp[1] stays 0, and so does every count that builds on it.
    6. Loop i over 2..=n. The first two entries are known, and the loop ends with dp[n]. For a one-digit string the range is empty.
    7. Single-digit case. If bytes[i - 1] isn't b'0', add dp[i - 1] to dp[i].
    8. Compute the last two digits as a number. A digit byte minus b'0' is the digit's value, so two is (bytes[i - 2] - b'0') * 10 + (bytes[i - 1] - b'0'). It is a u8, and at most 99, so it fits.
    9. Two-digit case. If two is between 10 and 26, add dp[i - 2] to dp[i].
    10. Return dp[n] with no semicolon.

    The solution in Rust

    impl Solution {
    fn num_decodings(s: String) -> i32 {
        let bytes = s.as_bytes();
        let n = bytes.len();
        let mut dp = vec![0i32; n + 1];
        dp[0] = 1;
        if bytes[0] != b'0' {
            dp[1] = 1;
        }
        for i in 2..=n {
            if bytes[i - 1] != b'0' {
                dp[i] += dp[i - 1];
            }
            let two = (bytes[i - 2] - b'0') * 10 + (bytes[i - 1] - b'0');
            if two >= 10 && two <= 26 {
                dp[i] += dp[i - 2];
            }
        }
        dp[n]
    }
}

    The table for a few inputs, printed from the same logic, shows how the counts build up:

    226    dp = [1, 1, 2, 3]
11106  dp = [1, 1, 2, 3, 2, 2]
06     dp = [1, 0, 0]
2101   dp = [1, 1, 2, 1, 1]

    For 226, dp[2] is 2 (the groups 2, 2 and 22), and dp[3] adds the single 6 after both of those (dp[2]) and the pair 26 after the single 2 (dp[1]), giving 3. For 11106 the entry dp[4] drops to 2: the 0 can't stand alone, so only the pair 10 counts, and dp[2] is its source.

    Rust details worth a closer look:

    • Bytes instead of characters. s.as_bytes() gives a &[u8], a view of the string's bytes with no copy. That is correct here because the input is digits only, and each digit is a single byte. Letters outside ASCII would take several bytes, but they don't occur in this problem.
    • Byte arithmetic. b'7' - b'0' is the u8 value 7, since digit characters are consecutive. The arithmetic stays in u8, which is enough for values up to 99.
    • usize indexes. i - 1 and i - 2 are safe because the loop starts at 2.
    • Indexing a one-digit string. dp[1] exists for every n of at least 1, because dp has n + 1 entries.
    • i32 counts. The lesson says the answer fits in 32 bits. In a build with optimizations, as the lessons use, an i32 that overflows wraps silently instead of stopping: a string of 100 ones, whose true count is larger than i32::MAX, gives -424332979. Inside the constraints that doesn't happen.

    Complexity

    Time: O(n). Each of the n entries takes a constant amount of work.

    Space: O(n). The table has n + 1 entries. Since each entry looks back only two places, two variables would be enough for O(1) space, but the table makes the idea easy to follow.

    Edge cases and common mistakes

    • Leading zero. "0" and "06" give 0.
    • A zero in the middle. A 0 must be part of a 10 or a 20. "10" gives 1 and "100" gives 0, because the last 0 follows a 0. "30" also gives 0: 30 is above 26 and the 0 can't stand alone. "1001" gives 0 too.
    • 27 and above. "27" gives 1, only 2 and 7, since 27 is not a letter.
    • Pairs below 10. A pair like 07 is not the letter 7. That's why the check is two >= 10, not just two <= 26.
    • A zero that is rescued. "2101" gives 1: the only valid split is 2, 10, 1.
    • A wrong base case. With dp[0] = 0, nothing would ever count. With dp[1] = 1 set unconditionally, strings starting with 0 would get a wrong count.
    • One digit. "1" gives 1, and the loop doesn't run.
    • Empty input. The constraints say the string has at least one digit. Reading bytes[0] of an empty string would panic.

    Testing

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