Code Logo

Decode Ways

Published at24 Jul 2026
Created by
Medium 0 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
Recommendation Algorithm Flow for Decode Ways

Solution Approach

DP: dp[i] = dp[i-1] (if 1-9) + dp[i-2] (if 10-26). Space-optimized with two variables.

function solution(s) {
  if (s.charAt(0) === '0') return 0;
  var a = 1, b = 1;
  for (var i = 1; i < s.length; i++) {
    var cur = 0;
    if (s.charAt(i) !== '0') cur += b;
    var two = parseInt(s.substring(i-1, i+1));
    if (two >= 10 && two <= 26) cur += a;
    a = b;
    b = cur;
  }
  return b;
}

Time O(n), Space O(1).

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;
    }
}