Decode Ways
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
Constraints
1 <= s.length <= 100s contains only digits and may contain leading zero(s).
Dynamic Programming (Space Optimized)
Approach
Let `dp[i]` be the number of ways to decode the substring of length `i`. If the current character is not '0', it can be decoded as a single digit, contributing `dp[i-1]` ways. If the previous character and the current character form a valid two-digit number between 10 and 26, it contributes `dp[i-2]` ways. Thus, `dp[i] = dp[i-1] + dp[i-2]` (under the valid conditions). Since we only need the last two values, we can optimize the space to O(1) just like Fibonacci/Climbing Stairs.
Complexity Analysis
Time complexity is O(n) because we iterate through the string once. Space complexity is O(1) as we only use variables to store the two previous states.
class Solution { public int numDecodings(String s) { if (s == null || s.length() == 0 || s.charAt(0) == '0') { return 0; } int n = s.length(); int prev2 = 1; // ways to decode empty string int prev1 = 1; // ways to decode first char for (int i = 1; i < n; i++) { int current = 0; // Single digit decode (1-9) if (s.charAt(i) != '0') { current += prev1; } // Two digit decode (10-26) int twoDigit = Integer.parseInt(s.substring(i - 1, i + 1)); if (twoDigit >= 10 && twoDigit <= 26) { current += prev2; } prev2 = prev1; prev1 = current; } return prev1; }}