Decode Ways

medium
Dynamic ProgrammingStringDynamic Programming

Given a string s containing only digits, return the number of ways to decode it. A message encoded with the mapping 'A' = 1, 'B' = 2, ..., 'Z' = 26 can be decoded by grouping digits into valid letter codes (1-26). The digit '0' cannot be mapped to any letter by itself but can form valid two-digit codes like 10 or 20.

Examples

Example 1

  • Input: s = "12"
  • Output: 2
  • Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

Example 2

  • Input: s = "226"
  • Output: 3
  • Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Example 3

  • Input: s = "06"
  • Output: 0
  • Explanation: "06" cannot be decoded because "06" is not a valid code (leading zero).

Constraints

  • 1 <= s.length <= 100
  • s contains only digits and may contain leading zeros.

Approaches

3 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Recursion (Brute Force)

Intuition

At each position we can decode one digit or two digits (if the two-digit number is between 10 and 26). We recursively count the total ways from the current position to the end. A digit '0' cannot start a valid code, so we return 0 for that branch. Without memoization, this has exponential time due to overlapping subproblems.

Algorithm

  1. If the current index equals the string length, return `1` (one valid decoding found).
  2. If the current character is `'0'`, return `0` (invalid).
  3. Count ways by decoding one digit and recursing from `index + 1`.
  4. If two digits form a number between 10 and 26, also add ways from `index + 2`.
  5. Return the total count.
TimeO(2^n)SpaceO(n) for the recursion stack

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int numDecodings(string s) {
        return helper(s, 0);
    }

    int helper(string& s, int i) {
        if (i == s.size()) return 1;
        if (s[i] == '0') return 0;
        int ways = helper(s, i + 1);
        if (i + 1 < s.size()) {
            int twoDigit = (s[i] - '0') * 10 + (s[i + 1] - '0');
            if (twoDigit >= 10 && twoDigit <= 26) {
                ways += helper(s, i + 2);
            }
        }
        return ways;
    }
};
Java 21
class Solution {
    public int numDecodings(String s) {
        return helper(s, 0);
    }

    private int helper(String s, int i) {
        if (i == s.length()) return 1;
        if (s.charAt(i) == '0') return 0;
        int ways = helper(s, i + 1);
        if (i + 1 < s.length()) {
            int twoDigit = Integer.parseInt(s.substring(i, i + 2));
            if (twoDigit >= 10 && twoDigit <= 26) {
                ways += helper(s, i + 2);
            }
        }
        return ways;
    }
}
Python 3.12
class Solution:
    def numDecodings(self, s: str) -> int:
        def helper(i: int) -> int:
            if i == len(s):
                return 1
            if s[i] == '0':
                return 0
            ways = helper(i + 1)
            if i + 1 < len(s) and 10 <= int(s[i:i + 2]) <= 26:
                ways += helper(i + 2)
            return ways

        return helper(0)
Go 1.26
func numDecodings(s string) int {
    var helper func(i int) int
    helper = func(i int) int {
        if i == len(s) {
            return 1
        }
        if s[i] == '0' {
            return 0
        }
        ways := helper(i + 1)
        if i+1 < len(s) {
            twoDigit := int(s[i]-'0')*10 + int(s[i+1]-'0')
            if twoDigit >= 10 && twoDigit <= 26 {
                ways += helper(i + 2)
            }
        }
        return ways
    }
    return helper(0)
}
Approach 2

Dynamic Programming (Bottom-Up)

Intuition

Define dp[i] as the number of ways to decode the substring s[i:]. We fill the table from right to left. If s[i] is not '0', dp[i] includes dp[i+1]. If the two-digit number s[i..i+1] is between 10 and 26, dp[i] also includes dp[i+2]. This eliminates redundant computation.

Algorithm

  1. Create array `dp` of size `n + 1` with `dp[n] = 1`.
  2. Iterate from `i = n - 1` down to `0`:
  3. Return `dp[0]`.
TimeO(n)SpaceO(n)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        vector<int> dp(n + 1, 0);
        dp[n] = 1;
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] == '0') {
                dp[i] = 0;
            } else {
                dp[i] = dp[i + 1];
                if (i + 1 < n) {
                    int twoDigit = (s[i] - '0') * 10 + (s[i + 1] - '0');
                    if (twoDigit >= 10 && twoDigit <= 26) {
                        dp[i] += dp[i + 2];
                    }
                }
            }
        }
        return dp[0];
    }
};
Java 21
class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        int[] dp = new int[n + 1];
        dp[n] = 1;
        for (int i = n - 1; i >= 0; i--) {
            if (s.charAt(i) == '0') {
                dp[i] = 0;
            } else {
                dp[i] = dp[i + 1];
                if (i + 1 < n) {
                    int twoDigit = Integer.parseInt(s.substring(i, i + 2));
                    if (twoDigit >= 10 && twoDigit <= 26) {
                        dp[i] += dp[i + 2];
                    }
                }
            }
        }
        return dp[0];
    }
}
Python 3.12
class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        dp = [0] * (n + 1)
        dp[n] = 1
        for i in range(n - 1, -1, -1):
            if s[i] == '0':
                dp[i] = 0
            else:
                dp[i] = dp[i + 1]
                if i + 1 < n and 10 <= int(s[i:i + 2]) <= 26:
                    dp[i] += dp[i + 2]
        return dp[0]
Go 1.26
func numDecodings(s string) int {
    n := len(s)
    dp := make([]int, n+1)
    dp[n] = 1
    for i := n - 1; i >= 0; i-- {
        if s[i] == '0' {
            dp[i] = 0
        } else {
            dp[i] = dp[i+1]
            if i+1 < n {
                twoDigit := int(s[i]-'0')*10 + int(s[i+1]-'0')
                if twoDigit >= 10 && twoDigit <= 26 {
                    dp[i] += dp[i+2]
                }
            }
        }
    }
    return dp[0]
}
Approach 3

Space-Optimized DP

Intuition

Since dp[i] depends only on dp[i+1] and dp[i+2], we can replace the array with two variables. This reduces space to O(1) while preserving the same logic as the bottom-up approach.

Algorithm

  1. Initialize `next1 = 1` (represents `dp[n]`) and `next2 = 0` (represents `dp[n+1]`).
  2. Iterate from `i = n - 1` down to `0`:
  3. Shift: `next2 = next1`, `next1 = current`.
  4. Return `next1`.
TimeO(n)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        int next1 = 1, next2 = 0;
        for (int i = n - 1; i >= 0; i--) {
            int curr = 0;
            if (s[i] != '0') {
                curr = next1;
                if (i + 1 < n) {
                    int twoDigit = (s[i] - '0') * 10 + (s[i + 1] - '0');
                    if (twoDigit >= 10 && twoDigit <= 26) {
                        curr += next2;
                    }
                }
            }
            next2 = next1;
            next1 = curr;
        }
        return next1;
    }
};
Java 21
class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        int next1 = 1, next2 = 0;
        for (int i = n - 1; i >= 0; i--) {
            int curr = 0;
            if (s.charAt(i) != '0') {
                curr = next1;
                if (i + 1 < n) {
                    int twoDigit = Integer.parseInt(s.substring(i, i + 2));
                    if (twoDigit >= 10 && twoDigit <= 26) {
                        curr += next2;
                    }
                }
            }
            next2 = next1;
            next1 = curr;
        }
        return next1;
    }
}
Python 3.12
class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        next1, next2 = 1, 0
        for i in range(n - 1, -1, -1):
            curr = 0
            if s[i] != '0':
                curr = next1
                if i + 1 < n and 10 <= int(s[i:i + 2]) <= 26:
                    curr += next2
            next2 = next1
            next1 = curr
        return next1
Go 1.26
func numDecodings(s string) int {
    n := len(s)
    next1, next2 := 1, 0
    for i := n - 1; i >= 0; i-- {
        curr := 0
        if s[i] != '0' {
            curr = next1
            if i+1 < n {
                twoDigit := int(s[i]-'0')*10 + int(s[i+1]-'0')
                if twoDigit >= 10 && twoDigit <= 26 {
                    curr += next2
                }
            }
        }
        next2 = next1
        next1 = curr
    }
    return next1
}

Frequently asked questions

What is the optimal time complexity of Decode Ways?

The most efficient approach in this guide ("Space-Optimized DP") runs in O(n) time and uses O(1) extra space. Earlier brute-force approaches are slower; see all 3 approaches above for the full progression.

What pattern does Decode Ways use?

Decode Ways is a medium-level Dynamic Programming problem involving String, Dynamic Programming. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Decode Ways be solved without extra space?

The most space-efficient approach in this guide uses O(1) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(n) for the recursion stack, while the optimized version uses O(1).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Original problem: leetcode.com

Loading editor...
Input
s=
"12"
Expected Output
2