Code Logo

Decode Ways

Published at24 Jul 2026
Created by
Medium 1 views
Like0

A message containing letters A-Z can be encoded to numbers using the mapping: A=1, B=2, ..., Z=26. Given a string s containing only digits, return the number of ways to decode it. For example, '12' can be decoded as 'AB' (1,2) or 'L' (12).

This is a classic 1D DP problem. At each position i, the number of ways depends on the previous positions. A single digit (1-9) can be decoded if non-zero. Two digits (10-26) can be decoded if they form a valid number between 10 and 26.

The recurrence is:dp[i] = (dp[i-1] if s[i] != '0') + (dp[i-2] if 10<= int(s[i-1:i+1]) <= 26). Base cases: dp[0] = 1 (empty string), and dp[1] = 1 if s[0] != '0'.

Edge cases include strings starting with '0' (return 0), strings like '10' or '20' which have only one valid decode, and strings with multiple zeros like '100' (return 0).

The decode ways DP is similar to a constrained Fibonacci sequence where each step conditionally adds the previous two values based on digit validity. The constraints make this medium difficulty: zeros cannot stand alone and two-digit codes must be between 10 and 26 inclusive.

Space optimization uses two variables for dp[i-1] and dp[i-2]. The presence of zeros heavily impacts the recurrence: a zero digit forces the two-digit code to include the previous digit, eliminating the single-digit decode option.

Example Input & Output

Example 1
Input
"12"
Output
2
Explanation

"12" -> AB(1,2) or L(12).

Example 2
Input
"0"
Output
0
Explanation

Leading zero, no valid decode.

Example 3
Input
"226"
Output
3
Explanation

BZ(2,26), VF(22,6), BBF(2,2,6).

Example 4
Input
"10"
Output
1
Explanation

Only "10" -> J(10).

Example 5
Input
"06"
Output
0
Explanation

Leading zero, invalid.

Algorithm Flow

Recommendation Algorithm Flow for Decode Ways

Solution Approach

Decode a numeric string where 'A'=1, 'B'=2, ..., 'Z'=26. Use dynamic programming where dp[i] is the number of ways to decode the first i characters. At each position, consider both single-digit (1-9) and two-digit (10-26) decodings. If the current digit is valid alone, add dp[i-1]. If the previous two digits form a valid number, add dp[i-2].

function numDecodings(s) {
  if (!s || s[0] === '0') return 0;
  var n = s.length, dp = Array(n + 1).fill(0);
  dp[0] = 1; dp[1] = 1;
  for (var i = 2; i <= n; i++) {
    var one = parseInt(s[i - 1]);
    var two = parseInt(s.substring(i - 2, i));
    if (one >= 1) dp[i] += dp[i - 1];
    if (two >= 10 && two <= 26) dp[i] += dp[i - 2];
  }
  return dp[n];
}

The recurrence accounts for the fact that '0' cannot start a valid single-digit decoding, and two-digit decodings are only valid for 10-26. Leading zeros make the string undecodable.

Time complexity is O(n), space complexity is O(n) or O(1) with rolling variables.

Best Answers

java
class Solution {
    public int solution(String s) {
        if (s.charAt(0)=='0') return 0;
        int a=1,b=1;
        for (int i=1;i<s.length();i++) {
            int cur=0;
            if (s.charAt(i)!='0') cur+=b;
            int two=Integer.parseInt(s.substring(i-1,i+1));
            if (two>=10&&two<=26) cur+=a;
            a=b;b=cur;
        }
        return b;
    }
}