Problem
You are given a strings containing digits. Each digit sequence can be decoded using the following mapping:
1 → A
2 → B
.
.
.
26 → Z0 cannot be decoded by itself. It can only appear as part of 10 or 20.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
s = "226"Output
32 2 6 → B B F
22 6 → V F
2 26 → B Z
Memoization Approach
To decode the string, we start at an index and decide how many digits to use. At each position, we can try to decode one digit or two digits.If the current digit is between
1 and 9, it can be decoded as one character, and we then move to the next index.
If the current digit together with the next digit forms a number between
10 and 26, the two digits can also be decoded as one character, and we then move two positions forward.
If we reach the end of the string, one complete decoding has been found. If the current character is
'0', it cannot be decoded by itself.
The same index can be reached through different decoding choices, so we store the result for each index using memoization.
class Solution {
public int numDecodings(String s) {
if (s == null || s.length() == 0)
return 0;
Integer[] memo = new Integer[s.length()];
return numDecodingsHelper(s, 0, memo);
}
private int numDecodingsHelper(String s, int i, Integer[] memo) {
// Reached the end, found one valid decoding
if (i == s.length())
return 1;
// A valid code cannot start with '0'
if (s.charAt(i) == '0')
return 0;
// Return the cached result
if (memo[i] != null)
return memo[i];
// Decode the current digit
int ways = numDecodingsHelper(s, i + 1, memo);
// Check if the next two digits form a valid code from 10 to 26
if (i + 1 < s.length()) {
int ten = s.charAt(i) - '0';
int one = s.charAt(i + 1) - '0';
int value = ten * 10 + one;
if (value >= 10 && value <= 26)
ways += numDecodingsHelper(s, i + 2, memo);
}
return memo[i] = ways;
}
}
Complexity
There aren possible indices, and each index is calculated only once, resulting in O(n) time complexity. The memoization array requires O(n) space.
Tabulation Approach
We can also solve the problem using bottom-up Dynamic Programming.Let
dp[i] represent the number of ways to decode the substring starting at index i. If we reach the end of the string, one valid decoding has been completed.
We then process the string from right to left. If the current digit is not
'0', it can be decoded by itself.
If the current digit and the next digit together form a number between
10 and 26, we can also decode both digits together.
class Solution {
public int numDecodings(String s) {
int n = s.length();
int[] dp = new int[n + 1];
// One way to decode an empty suffix.
dp[n] = 1;
for (int i = n - 1; i >= 0; i--) {
// A zero cannot be decoded by itself.
if (s.charAt(i) == '0') {
dp[i] = 0;
continue;
}
// Decode one digit.
dp[i] = dp[i + 1];
// Decode two digits.
if (i + 1 < n) {
int number = (s.charAt(i) - '0') * 10 + (s.charAt(i + 1) - '0');
if (number >= 10 && number <= 26) {
dp[i] += dp[i + 2];
}
}
}
return dp[0];
}
}
Complexity
Each position is processed once, resulting inO(n) time complexity, while the DP array requires O(n) space.
Space Optimized Approach
In the tabulation approach,dp[i] only depends on dp[i + 1] and dp[i + 2].
Therefore, instead of storing the entire DP array, we only need to keep track of the previous two values.
class Solution {
public int numDecodings(String s) {
int n = s.length();
int next = 1;
int nextNext = 0;
for (int i = n - 1; i >= 0; i--) {
int current = 0;
// Decode one digit.
if (s.charAt(i) != '0') {
current = next;
// Decode two digits.
if (i + 1 < n) {
int number = (s.charAt(i) - '0') * 10 + (s.charAt(i + 1) - '0');
if (number >= 10 && number <= 26) {
current += nextNext;
}
}
}
nextNext = next;
next = current;
}
return next;
}
}
Complexity
Each character is processed once, resulting inO(n) time complexity, and only a constant number of variables is used, resulting in O(1) space complexity.