A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
Input Format:
The first and the only argument is a string A.
Output Format:
Return an integer, representing the number of ways to decode the string.
Constraints:
1 <= length(A) <= 1e5
Example :
Input 1:
A = "8"
Output 1:
1
Explanation 1:
Given encoded message "8", it could be decoded as only "H" (8).
The number of ways decoding "8" is 1.
Input 2:
A = "12"
Output 2:
2
Explanation 2:
Given encoded message "12", it could be decoded as "AB" (1, 2) or "L" (12).
The number of ways decoding "12" is 2.
Method:
If prev and current element is <= 26, then the possible ways of decode is dp[i - 2] + dp[i - 1] because we can either choose to treat the number separately, in which we would use dp[i - 1], or treat them as a whole, in which we would use dp[i - 2].
Solution:
Time: O(n) Space: O(n)
class Solution {
public int numDecodings(String s) {
// "123145487842120"
char[] arr = s.toCharArray();
int n = arr.length;
if (arr[0] == '0') return 0;
int[] dp = new int[n];
dp[0] = 1;
for (int i = 1; i < n; i ++) {
int c = arr[i] - '0';
int p = arr[i - 1] - '0';
if (p != 1 && p != 2 && c == 0) return 0;
if ((p == 1 || (p == 2 && c <= 6)) && c != 0) {
if (i >= 2) {
dp[i] = dp[i - 1] + dp[i - 2];
} else {
dp[i] = 2;
}
} else if (p <= 2 && c == 0) {
if (i >= 2) {
dp[i] = dp[i - 2];
} else {
dp[i] = 1;
}
} else {
dp[i] = dp[i - 1];
}
}
return dp[n - 1];
}
}