Number of Ways to Decode a Message

Prereq: Memoization Intro

We have a message consisting of digits 0-9 to decode. Letters are encoded to digits by their positions in the alphabet

1A -> 1
2B -> 2
3C -> 3
4...
5Y -> 25
6Z -> 26

Given a non-empty string of digits, how many ways are there to decode it?

Input: "18"

Output: 2

Explanation: "18" can be decoded as "AH" or "R"

Input: "123"

Output: 3

Explanation: "123" can be decoded as "ABC", "LC", "AW"

Try it yourself

Solution

We can start from the beginning of the string and try to decode each digit in the string until we get to the end of the string.

Each digit 1-9 maps to an alphabet.

For digits 1 and 2 there is a possibility to decode two consecutive digits together.

For example, there are two ways to decode 12:

1 => A and 2 => B
12 => L.

There are two ways to decode 26:

2 => B, 6 => F
26 => Z.

There is only one way to decode 27.

2 => B and 7 => G because there is no 27th alphabet.

It's impossible to decode a string with a leading 0, such as 02, because 0 does not map to any alphabet. The only way to decode a string with 0 is to have a preceding 1 or 2 and decode as 10 and 20, respectively.

So depending on the current and following digit, there could be zero to two ways to branch out. Here is how the state-space tree looks like:

Impementation

1function dfs(start_index, [...additional states]):
2    if is_leaf(start_index):
3        return 1
4    ans = initial_value
5    for edge in get_edges(start_index, [...additional states]):
6        if additional states: 
7            update([...additional states])
8        ans = aggregate(ans, dfs(start_index + len(edge), [...additional states]))
9        if additional states: 
10            revert([...additional states])
11    return ans
12

1private static int dfs(Integer startIndex, List<T> target) {
2    if (isLeaf(startIndex)) {
3        return 1;
4    }
5
6    ans = initialValue;
7    for (T edge : getEdges(startIndex, [...additional states])) {
8        if (additional states) {
9            update([...additional states]);
10        }
11        ans = aggregate(ans, dfs(startIndex + edge.length(), [...additional states])
12        if (additional states) {
13            revert([...additional states]);
14        }
15    }
16    return ans;
17}
18

1function dfs(startIndex, target) {
2    if (isLeaf(startIndex)) {
3        return 1
4    }
5    int ans = initialValue;
6    for (const edge of getEdges(startIndex, [...additional states])) {
7        if (additional states) {
8            update([...additional states]);
9        }
10        ans = aggregate(ans, dfs(startIndex + edge.length(), [...additional states])
11        if (additional states) {
12            revert([...additional states]);
13        }
14    }
15    return ans;
16}
17

1int dfs(int startIndex, std::vector<T>& target) {
2    if (isValid(target[startIndex:])) {
3        return 1;
4    }
5    int counter = 0;
6    for (auto edge : getEdges(startIndex, [...additional states])) {
7        if (additional states) {
8            update([...additional states]);
9        }
10        ans = aggregate(ans, dfs(startIndex + edge.length(), [...additional states])
11        if (additional states) {
12            revert([...additional states]);
13        }
14    }
15    return ans;
16}
17

1public static int Dfs(int startIndex, List<T> target)
2{
3    if (IsLeaf(startIndex))
4    {
5        return 1;
6    }
7    int ans = initialValue;
8    foreach (T edge : getEdges(startIndex, [...additional states]))
9    {
10        if (additional states) {
11            update([...additional states]);
12        }
13        ans = aggregate(ans, dfs(startIndex + edge.length(), [...additional states])
14        if (additional states) {
15            revert([...additional states]);
16        }
17    }
18    return ans;
19}
20

1func dfs(startIndex int, additionalStates <T>[]) int {
2    if isLeaf(startIndex) {
3        return 1
4    }
5    ans := initialValue
6    for _, edge := range getEdges(startIndex, [...additionalStates]) {
7        if additionalStates{
8            update([...additionalStates])
9        }
10        ans = aggregate(ans, dfs(startIndex+len(edge), [...additionalStates]))
11        if additionalStates {
12            revert([...additionalStates])
13        }
14    }
15    return ans
16}
17

And fill out the missing logic:

is_leaf: if start_index reaches the digits.length then we have matched every digit and the decoding is done.
get_edges: we use startIndex to record the next digit to match. We can always match one digit first. If there are two consecutive digits that falls in 10-26 then we can match two digits.
initial_value: we start with 0 because we haven't matched anything.
aggregate: we add the number of ways to decode from the subtree.
additional states: there are no additional states; we have all the information to determine how to branch out.

1def decode_ways(digits):
2    def dfs(start_index):
3        if start_index == len(digits):
4            return 1
5
6        ways = 0
7        # can't decode string with leading 0
8        if digits[start_index] == '0':
9          return ways
10        # decode one digit
11        ways += dfs(start_index + 1)
12        # decode two digits
13        if 10 <= int(digits[start_index: start_index + 2]) <= 26:
14            ways += dfs(start_index + 2)
15
16        return ways
17
18    return dfs(0)
19

1private static int dfs(int startIndex, String digits) {
2    if (startIndex == digits.length()) return 1;
3
4    int ways = 0;
5    // can't decode string with leading 0
6    if (digits.charAt(startIndex) == '0') {
7      return ways;
8    }
9    // decode one digit
10    ways += dfs(startIndex + 1, digits);
11    // decode two digits
12    if (startIndex + 2 <= digits.length() && Integer.parseInt(digits.substring(startIndex, startIndex + 2)) <= 26) {
13        ways += dfs(startIndex + 2, digits);
14    }
15
16    return ways;
17}
18
19public static int decodeWays(String digits) {
20    return dfs(0, digits);
21}
22

1function decodeWays(digits) {
2    return dfs(0, digits);
3}
4
5function dfs(startIndex, digits) {
6    if (startIndex === digits.length) return 1;
7
8    let ways = 0;
9    // can't decode string with leading 0
10    if (digits[startIndex] == "0") {
11      return ways;
12    }
13    // decode one digit
14    ways += dfs(startIndex + 1, digits);
15    // decode two digits
16    if (startIndex + 2 <= digits.length && parseInt(digits.substring(startIndex, startIndex + 2)) <= 26) {
17        ways += dfs(startIndex + 2, digits);
18    }
19
20    return ways;
21}
22

1int dfs(int startIndex, std::string digits) {
2    if (startIndex == digits.length()) return 1;
3
4    int ways = 0;
5    // can't decode string with leading 0
6    if (digits[startIndex] == '0') {
7      return ways;
8    }
9    // decode one digit
10    ways += dfs(startIndex + 1, digits);
11    // decode two digits
12    if (startIndex + 2 <= digits.length() && stoi(digits.substr(startIndex, 2)) <= 26) {
13        ways += dfs(startIndex + 2, digits);
14    }
15    return ways;
16}
17
18int decode_ways(std::string digits) {
19    return dfs(0, digits);
20}
21

1private static int Dfs(int startIndex, string digits)
2{
3    if (startIndex == digits.Length) return 1;
4    int ways = 0;
5    // can't decode string with leading 0
6    if (digits[startIndex] == '0') {
7      return ways;
8    }
9    // decode one digit
10    ways += Dfs(startIndex + 1, digits);
11    // decode two digits
12    if (startIndex + 2 <= digits.Length && int.Parse(digits.Substring(startIndex, 2)) <= 26) {
13        ways += Dfs(startIndex + 2, digits);
14    }
15    return ways;
16}
17
18public static int DecodeWays(string digits)
19{
20    return Dfs(0, digits);
21}
22

1func decodeWays(digits string) int {
2    var dfs func(startIndex int) int
3    dfs = func(startIndex int) int {
4        if startIndex == len(digits) {
5            return 1
6        }
7        ways := 0
8        // can't decode string with leading 0
9        if digits[startIndex] == '0' {
10            return ways
11        }
12        // decode one digit
13        ways += dfs(startIndex + 1)
14        // decode two digits
15        if startIndex+1 < len(digits) {
16            twoDigits, _ := strconv.Atoi(digits[startIndex : startIndex+2])
17            if 10 <= twoDigits && twoDigits <= 26 {
18                ways += dfs(startIndex + 2)
19            }
20        }
21        return ways
22    }
23
24    return dfs(0)
25}
26

Time Complexity

In the worst case, every digit can be decoded in two ways. With n digits, there are O(2^n) nodes in the state-space tree. We do O(1) operation for each node so the overall time complexity is O(2^n).

Memoization

Similar to the previous problem, we see there are duplicated subtrees.

The green subtree and the red subtree contains the exact same content 3 and had the same prefix 12. The green subtree is visited before the red subtree and we can memoize the results from green subtree by keeping a memo array that records the start_index of the remaining strings to be decoded.

1def decode_ways(digits):
2    memo = {}
3    def dfs(start_index, memo):
4        if start_index in memo:
5            return memo[start_index]
6        if start_index == len(digits):
7            return 1
8
9        ways = 0
10        # can't decode string with leading 0
11        if digits[start_index] == '0':
12            return ways
13        # decode one digit
14        ways += dfs(start_index + 1, memo)
15        # decode two digits
16        if 10 <= int(digits[start_index: start_index + 2]) <= 26:
17            ways += dfs(start_index + 2, memo)
18        
19        memo[start_index] = ways
20        return ways
21
22    return dfs(0, memo)
23
24if __name__ == '__main__':
25    digits = input()
26    res = decode_ways(digits)
27    print(res)
28

1import java.util.Arrays;
2import java.util.List;
3import java.util.Scanner;
4import java.util.stream.Collectors;
5import java.util.stream.IntStream;
6
7class Solution {
8    private static int dfs(int startIndex, String digits, int[] memo) {
9        if (startIndex == digits.length()) return 1;
10        if (memo[startIndex] != -1) return memo[startIndex];
11
12        int ways = 0;
13        // can't decode string with leading 0
14        if (digits.charAt(startIndex) == '0') {
15            return ways;
16        }
17        // decode one digit
18        ways += dfs(startIndex + 1, digits, memo);
19        // decode two digits
20        if (startIndex + 2 <= digits.length() && Integer.parseInt(digits.substring(startIndex, startIndex + 2)) <= 26) {
21            ways += dfs(startIndex + 2, digits, memo);
22        }
23        memo[startIndex] = ways;
24
25        return ways;
26    }
27
28    public static int decodeWays(String digits) {
29        int[] memo = new int[digits.length()];
30        Arrays.fill(memo, -1);
31        return dfs(0, digits, memo);
32    }
33
34    public static void main(String[] args) {
35        Scanner scanner = new Scanner(System.in);
36        String digits = scanner.nextLine();
37        scanner.close();
38        int res = decodeWays(digits);
39        System.out.println(res);
40    }
41}
42

1using System;
2
3class Solution
4{
5    private static int Dfs(int startIndex, string digits, int[] memo)
6    {
7        if (startIndex == digits.Length) return 1;
8        if (memo[startIndex] != -1) return memo[startIndex];
9        int ways = 0;
10        // can't decode string with leading 0
11        if (digits[startIndex] == '0') {
12          return ways;
13        }
14        // decode one digit
15        ways += Dfs(startIndex + 1, digits, memo);
16        // decode two digits
17        if (startIndex + 2 <= digits.Length && int.Parse(digits.Substring(startIndex, 2)) <= 26) {
18            ways += Dfs(startIndex + 2, digits, memo);
19        }
20        memo[startIndex] = ways;
21        return ways;
22    }
23
24    public static int DecodeWays(string digits)
25    {
26        int[] memo = new int[digits.Length];
27        Array.Fill(memo, -1);
28        return Dfs(0, digits, memo);
29    }
30
31    public static void Main()
32    {
33        string digits = Console.ReadLine();
34        int res = DecodeWays(digits);
35        Console.WriteLine(res);
36    }
37}
38

1function decodeWays(digits) {
2    let memo = {};
3    return dfs(0, digits, memo);
4}
5
6function dfs(startIndex, digits, memo) {
7    if (startIndex === digits.length) return 1;
8    if (startIndex in memo) return memo[startIndex];
9
10    let ways = 0;
11    // can't decode string with leading 0
12    if (digits[startIndex] == "0") {
13        return ways;
14    }
15    // decode one digit
16    ways += dfs(startIndex + 1, digits, memo);
17    // decode two digits
18    if (startIndex + 2 <= digits.length && parseInt(digits.substring(startIndex, startIndex + 2)) <= 26) {
19        ways += dfs(startIndex + 2, digits, memo);
20    }
21    memo[startIndex] = ways;
22
23    return ways;
24}
25
26function* main() {
27    const digits = yield;
28    const res = decodeWays(digits);
29    console.log(res);
30}
31
32class EOFError extends Error {}
33{
34    const gen = main();
35    const next = (line) => gen.next(line).done && process.exit();
36    let buf = '';
37    next();
38    process.stdin.setEncoding('utf8');
39    process.stdin.on('data', (data) => {
40        const lines = (buf + data).split('\n');
41        buf = lines.pop();
42        lines.forEach(next);
43    });
44    process.stdin.on('end', () => {
45        buf && next(buf);
46        gen.throw(new EOFError());
47    });
48}
49

1#include <iostream> // cin, cout
2#include <string> // getline
3
4int dfs(int startIndex, std::string digits, int memo[]) {
5    if (startIndex == digits.length()) return 1;
6    if (memo[startIndex] != -1) return memo[startIndex];
7    
8    int ways = 0;
9    // can't decode string with leading 0
10    if (digits[startIndex] == '0') {
11      return ways;
12    }
13    // decode one digit
14    ways += dfs(startIndex + 1, digits, memo);
15    // decode two digits
16    if (startIndex + 2 <= digits.length() && stoi(digits.substr(startIndex, 2)) <= 26) {
17        ways += dfs(startIndex + 2, digits, memo);
18    }
19    memo[startIndex] = ways;
20    return ways;
21}
22
23int decode_ways(std::string digits) {
24    int memo[digits.length()];
25    std::fill_n(memo, digits.length(), -1);
26    return dfs(0, digits, memo);
27}
28
29int main() {
30    std::string digits;
31    std::getline(std::cin, digits);
32    int res = decode_ways(digits);
33    std::cout << res << '\n';
34}
35

1package main
2
3import (
4    "bufio"
5    "fmt"
6    "os"
7    "strconv"
8)
9
10func decodeWays(digits string) int {
11    memo := make(map[int]int)
12
13    var dfs func(startIndex int) int
14    dfs = func(startIndex int) int {
15        if val, ok := memo[startIndex]; ok {
16            return val
17        }
18        if startIndex == len(digits) {
19            return 1
20        }
21        ways := 0
22        // can't decode string with leading 0
23        if digits[startIndex] == '0' {
24            return ways
25        }
26        // decode one digit
27        ways += dfs(startIndex + 1)
28        // decode two digits
29        if startIndex+1 < len(digits) {
30            twoDigits, _ := strconv.Atoi(digits[startIndex : startIndex+2])
31            if 10 <= twoDigits && twoDigits <= 26 {
32                ways += dfs(startIndex + 2)
33            }
34        }
35        memo[startIndex] = ways
36        return ways
37    }
38
39    return dfs(0)
40}
41
42func main() {
43    scanner := bufio.NewScanner(os.Stdin)
44    scanner.Scan()
45    digits := scanner.Text()
46    res := decodeWays(digits)
47    fmt.Println(res)
48}
49

Time complexity

The time complexity of the memoization solution is the size of the memo array O(n) multiplied by the number of operations per state which is O(1). So the overall time complexity is O(n).

Space complexity

The height of the state-space tree is at most O(n). The size of the memo array is O(n). Therefore the space complexity is O(n).

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

Number of Ways to Decode a Message

Try it yourself

Solution

Impementation

Time Complexity

Memoization

Time complexity

Space complexity