Decode Ways

Medium Problem 122 of 151 Java and Python

Problem

A message of letters A–Z is encoded as numbers: A → 1, B → 2, …, Z → 26. Given a string s of digits, return how many ways it can be decoded.

A group cannot start with 0 (so "06" is not valid), and the answer fits in a 32-bit integer.

Example 1

Input: s = "12"
Output: 2
Why: "AB" (1 2) or "L" (12).

Example 2

Input: s = "226"
Output: 3
Why: "BZ" (2 26), "VF" (22 6) or "BBF" (2 2 6).

Example 3

Input: s = "06"
Output: 0

Constraints

1 ≤ s.length ≤ 100
s contains only digits and may contain leading zeros.

Explanation

Like Climbing Stairs, each step uses one or two digits. ways(i) (decodings of the first i digits) adds ways(i - 1) if the last digit alone is 1–9, and ways(i - 2) if the last two digits form 10–26.

Approach 1 · Naive

Plain recursion

Time O(2ⁿ)
Space O(n)

From position i, decode one digit or two digits (if valid) and recurse.

count(i): if i == n, return 1; if s[i] == '0', return 0.
Add count(i + 1), plus count(i + 2) if s[i..i+1] is ≤ 26.

Java

class Solution {
    public int numDecodings(String s) {
        return count(s, 0);
    }

    private int count(String s, int i) {
        if (i == s.length()) {
            return 1;
        }
        if (s.charAt(i) == '0') {
            return 0;
        }
        int ways = count(s, i + 1);
        if (i + 1 < s.length() && Integer.parseInt(s.substring(i, i + 2)) <= 26) {
            ways += count(s, i + 2);
        }
        return ways;
    }
}

Python

class Solution:
    def numDecodings(self, s: str) -> int:
        def count(i):
            if i == len(s):
                return 1
            if s[i] == "0":
                return 0
            ways = count(i + 1)
            if i + 1 < len(s) and int(s[i:i + 2]) <= 26:
                ways += count(i + 2)
            return ways

        return count(0)

Approach 2 · Optimal

Bottom-up with two variables

Time O(n)
Space O(1)

Walk the digits, keeping the number of decodings of the prefix ending one and two digits back.

prev2 = 1 (empty prefix), prev1 = 1 if s[0] != '0' else 0.
For i from 1: current = 0; add prev1 if s[i] is 1–9; add prev2 if s[i-1..i] is 10–26.
Shift the variables; return prev1.

Java

class Solution {
    public int numDecodings(String s) {
        int prev2 = 1;
        int prev1 = s.charAt(0) == '0' ? 0 : 1;
        for (int i = 1; i < s.length(); i++) {
            int current = 0;
            if (s.charAt(i) != '0') {
                current += prev1;
            }
            int two = (s.charAt(i - 1) - '0') * 10 + (s.charAt(i) - '0');
            if (two >= 10 && two <= 26) {
                current += prev2;
            }
            prev2 = prev1;
            prev1 = current;
        }
        return prev1;
    }
}

Python

class Solution:
    def numDecodings(self, s: str) -> int:
        prev2, prev1 = 1, 0 if s[0] == "0" else 1
        for i in range(1, len(s)):
            current = prev1 if s[i] != "0" else 0
            if 10 <= int(s[i - 1:i + 1]) <= 26:
                current += prev2
            prev2, prev1 = prev1, current
        return prev1

Complexity compared

Approach	Time	Space
Naive Plain recursion	O(2ⁿ)	O(n)
Optimal Bottom-up with two variables	O(n)	O(1)

Key takeaways

Zeros are the whole difficulty: "10" and "20" are valid, "30" and "06" are not.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem