Approach

Decode Ways

Problem Statement

A message containing letters from A-Z can be encoded into numbers using the following mapping:

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:

"AAJF" with the grouping (1 1 10 6)
"KJF" with the grouping (11 10 6)

Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

Given a string s containing only digits, return the number of ways to decode it.

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 mapped to "F" because of the leading zero ("6" is different from "06").

Constraints

1 ≤ s.length ≤ 100
s contains only digits and may contain leading zero(s).

Approach

Key Insight

This is a Dynamic Programming problem similar to Climbing Stairs!

At each position, we can decode:

Single digit (if valid: 1-9)
Two digits (if valid: 10-26)

dp[i] = ways to decode s[0:i]

If s[i-1] is valid single digit: add dp[i-1]
If s[i-2:i] is valid two digits: add dp[i-2]

Solution 1: Dynamic Programming

Build DP array bottom-up.

Algorithm:

Create dp array of size n+1
dp[0] = 1 (empty string has one way)
dp[1] = 1 if s[0] != '0', else 0
For each position i from 2 to n:
- Single digit: if s[i-1] != '0': dp[i] += dp[i-1]
- Two digits: if 10 ≤ int(s[i-2:i]) ≤ 26: dp[i] += dp[i-2]
Return dp[n]

Solution 2: Space-Optimized DP

Only need last two values.

Algorithm:

Keep prev2 and prev1
For each position:
- Calculate current based on single/double digit
- Update prev2 = prev1, prev1 = current
Return prev1

Solution 3: Recursion with Memoization

Top-down approach.

Algorithm:

Recursively try single and double digit decoding
Cache results for each position
Sum valid decoding paths

Complexity Analysis

DP Solution:

Time Complexity: O(n) - single pass
Space Complexity: O(n) - DP array (or O(1) if optimized)

Recursive with Memo:

Time Complexity: O(n) - each position computed once
Space Complexity: O(n) - memo + recursion stack

Pattern Recognition

This problem demonstrates:

Dynamic Programming with decision making
String validation logic
Fibonacci-like recurrence relation
Edge cases with zeros
Similar to Climbing Stairs but with constraints

Solution

java

1import java.util.*;
2
3class Solution {
4    // Solution 1: Dynamic Programming
5    public int numDecodings(String s) {
6        if (s == null || s.length() == 0 || s.charAt(0) == '0') {
7            return 0;
8        }
9
10        int n = s.length();
11        int[] dp = new int[n + 1];
12        dp[0] = 1;  // Empty string
13        dp[1] = 1;  // First character
14
15        for (int i = 2; i <= n; i++) {
16            // Single digit decode
17            if (s.charAt(i - 1) != '0') {
18                dp[i] += dp[i - 1];
19            }
20
21            // Two digit decode
22            int twoDigit = Integer.parseInt(s.substring(i - 2, i));
23            if (twoDigit >= 10 && twoDigit <= 26) {
24                dp[i] += dp[i - 2];
25            }
26        }
27
28        return dp[n];
29    }
30
31    // Solution 2: Space-Optimized DP
32    public int numDecodingsOptimized(String s) {
33        if (s == null || s.length() == 0 || s.charAt(0) == '0') {
34            return 0;
35        }
36
37        int prev2 = 1;  // dp[0]
38        int prev1 = 1;  // dp[1]
39
40        for (int i = 2; i <= s.length(); i++) {
41            int current = 0;
42
43            // Single digit
44            if (s.charAt(i - 1) != '0') {
45                current += prev1;
46            }
47
48            // Two digits
49            int twoDigit = Integer.parseInt(s.substring(i - 2, i));
50            if (twoDigit >= 10 && twoDigit <= 26) {
51                current += prev2;
52            }
53
54            prev2 = prev1;
55            prev1 = current;
56        }
57
58        return prev1;
59    }
60
61    // Solution 3: Recursion with Memoization
62    private Map<Integer, Integer> memo = new HashMap<>();
63
64    public int numDecodingsMemo(String s) {
65        return decode(s, 0);
66    }
67
68    private int decode(String s, int index) {
69        // Base case: reached end
70        if (index == s.length()) {
71            return 1;
72        }
73
74        // Leading zero
75        if (s.charAt(index) == '0') {
76            return 0;
77        }
78
79        // Check memo
80        if (memo.containsKey(index)) {
81            return memo.get(index);
82        }
83
84        // Single digit decode
85        int ways = decode(s, index + 1);
86
87        // Two digit decode
88        if (index + 1 < s.length()) {
89            int twoDigit = Integer.parseInt(s.substring(index, index + 2));
90            if (twoDigit <= 26) {
91                ways += decode(s, index + 2);
92            }
93        }
94
95        memo.put(index, ways);
96        return ways;
97    }
98
99    // Solution 4: Clean DP
100    public int numDecodingsClean(String s) {
101        if (s == null || s.length() == 0 || s.charAt(0) == '0') {
102            return 0;
103        }
104
105        int twoBack = 1;
106        int oneBack = 1;
107
108        for (int i = 1; i < s.length(); i++) {
109            int current = 0;
110
111            // Check single digit
112            if (s.charAt(i) != '0') {
113                current = oneBack;
114            }
115
116            // Check two digits
117            int twoDigit = Integer.parseInt(s.substring(i - 1, i + 1));
118            if (twoDigit >= 10 && twoDigit <= 26) {
119                current += twoBack;
120            }
121
122            twoBack = oneBack;
123            oneBack = current;
124        }
125
126        return oneBack;
127    }
128}
129