1. Problem statement

You’ve intercepted a secret message encoded as a string of digits. Your task is to determine how many different ways this string can be decoded into letters, based on the following mapping:

"1"  → 'A'  
"2"  → 'B'  
...  
"26" → 'Z'

Rules:

• A single digit (like "1") or a pair of digits (like "12") can be decoded if it falls within the range "1" to "26".
• A leading zero (like "06") is not valid and cannot be decoded.
• You must decode the entire string, and you can only decode contiguous digits from left to right.
• Return the total number of valid ways to decode the string.
• If no valid decoding is possible, return 0.

Example 1:

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

Example 2:

Input:  "226"
Output: 3
Explanation: "226" can be decoded as:
- "BZ"  (2 26)
- "VF"  (22 6)
- "BBF" (2 2 6)

2. How the Solution Works

Imagine you’re walking along the string from left to right. At every position, you’re asking:

“How many ways can I decode everything up to this point?”

You use a list (we call it dp[]) where:

dp[i] tells you how many ways you can decode the first i characters of the string.

At each step:

You look at:

1. The last 1 digit → is it valid? (i.e., not "0")
2. The last 2 digits → is it a number between "10" and "26"?

If it’s valid, you add the number of ways from the earlier position.

3. Visual Representation Example: "226"

We create an array dp[] like this:

s = "2  2  6"
      ↑  ↑  ↑
i =   1  2  3

dp[0] = 1     // Base case: empty string → 1 way
dp[1] = 1     // '2' is valid → 1 way
dp[2] = 2     // '2' and '22' are valid → 2 ways: [2,2] and [22]
dp[3] = 3     // '6' is valid, '26' is also valid → 3 ways total

3.1 How the decoding works

"226" can be split as:
1. [2, 2, 6] → B B F
2. [22, 6]   → V F
3. [2, 26]   → B Z
→ Total: 3 ways

4. Java implementation

public class DecodeWays {

    public int numDecodings(String s) {
        if (s == null || s.length() == 0) return 0;

        int n = s.length();
        int[] dp = new int[n + 1]; // dp[i] represents #ways to decode s[0..i-1]

        dp[0] = 1; // base case: empty string

        // base case: one character
        dp[1] = s.charAt(0) != '0' ? 1 : 0;

        for (int i = 2; i <= n; i++) {
            char oneDigitChar = s.charAt(i - 1);
            char twoDigitFirstChar = s.charAt(i - 2);

            // Check single digit
            if (oneDigitChar != '0') {
                dp[i] += dp[i - 1];
            }

            // Check two-digit number from s[i-2] and s[i-1]
            int twoDigit = Integer.parseInt(s.substring(i - 2, i));
            if (twoDigit >= 10 && twoDigit <= 26) {
                dp[i] += dp[i - 2];
            }
        }

        return dp[n];
    }
}