Problem Overview

You are given a string s containing only digits (0–9). The goal is to determine how many possible ways there are to decode the string into letters, where:

• 'A' → "1", 'B' → "2", … 'Z' → "26"

Each number from 1 to 26 corresponds to an uppercase English letter.

You need to find how many different ways the string can be decoded into letters.

Example 1:

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

Example 2:

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

Example 3:

Input: s = "06"
Output: 0
Explanation: A number cannot start with zero, so it is invalid.

---

Intuition and Approach

This problem can be solved using Dynamic Programming (DP) because:

• The total number of ways to decode a string depends on smaller subproblems — specifically, the number of ways to decode prefixes of the string.
• At each step, we can decode one digit or two digits (if valid).

We will build a dp array where:

• dp[i] represents the number of ways to decode the substring s[0...i-1].

---

Key Observations

1. If the string starts with ‘0’, it’s invalid because no letter maps to zero.
2. For each position i in the string,
   • If the current digit (i.e., s[i-1]) is not '0', we can take it as a single-digit decode (e.g., 1 → A).
     So we add dp[i-1] ways.
   • If the two-digit number formed by s[i-2]s[i-1] lies between 10 and 26, we can decode it as a two-digit decode (e.g., 12 → L).
     So we add dp[i-2] ways.

---

Step-by-Step Algorithm

1. If the input string is empty or starts with '0', return 0.
2. Let n = s.length().
3. Create a DP array dp of size n + 1.
4. Initialize: dp[0] = 1 // empty string has 1 way (base case) dp[1] = 1 // if the first char is valid (not '0')
5. For i from 2 to n:
   • If s[i-1] is not '0', add dp[i-1].
   • If the substring s[i-2..i-1] forms a number between 10 and 26, add dp[i-2].
6. Return dp[n] as the total number of ways.

---

Java Code Implementation

public class DecodeWays {

    public int numDecodings(String s) {
        if (s == null || s.length() == 0 || s.charAt(0) == '0') return 0;
        
        int n = s.length();
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        
        for (int i = 2; i <= n; i++) {
            int oneDigit = Integer.parseInt(s.substring(i - 1, i));
            int twoDigits = Integer.parseInt(s.substring(i - 2, i));
            
            if (oneDigit != 0) {
                dp[i] += dp[i - 1];
            }
            
            if (twoDigits >= 10 && twoDigits <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        
        return dp[n];
    }
}

---

Example Walkthrough

Let’s take s = "226"

i	s[i-1]	s[i-2..i-1]	dp[i] Calculation	dp[i]
0	–	–	base case	1
1	‘2’	–	valid single → dp[1]=1	1
2	‘2’	“22”	dp[2]=dp[1]+dp[0]=1+1	2
3	‘6’	“26”	dp[3]=dp[2]+dp[1]=2+1	3

Answer = 3

---

Complexity Analysis

• Time Complexity: O(n)
  We traverse the string once, doing constant work per character.
• Space Complexity: O(n)
  We use a DP array of size n + 1.

We can optimize to O(1) space using two variables to track the last two states.

---

Optimized Space Version

public class DecodeWaysOptimized {

    public int numDecodings(String s) {
        if (s == null || s.length() == 0 || s.charAt(0) == '0') return 0;
        
        int n = s.length();
        int prev = 1;  // dp[i-2]
        int curr = 1;  // dp[i-1]
        
        for (int i = 2; i <= n; i++) {
            int temp = 0;
            int oneDigit = Integer.parseInt(s.substring(i - 1, i));
            int twoDigits = Integer.parseInt(s.substring(i - 2, i));
            
            if (oneDigit != 0) temp += curr;
            if (twoDigits >= 10 && twoDigits <= 26) temp += prev;
            
            prev = curr;
            curr = temp;
        }
        
        return curr;
    }
}

---

Edge Cases to Consider

1. "0" → invalid, output 0.
2. "06" → invalid, output 0.
3. "10" → only “J”, output 1.
4. "101" → valid sequence → “JA”, output 1.
5. "11106" → multiple valid decodings but zeros restrict combinations.