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.
For example,
Given encoded message"12"
, it could be decoded as"AB"
(1 2) or"L"
(12). The number of ways decoding"12"
is 2.
Solution: dp[i]:前i个字母的组合数。2种情况:当前位数 > 0时,dp[i] += dp[i - 1];上一位数不为0且合起来 < 26时,dp[i] += dp[i - 2].
dp[0] = 1, dp[1] = 1(第一个字母不为0)
public int numDecodings(String s) {
if (s == null || s.length() == 0 || s.charAt(0) == '0') {
return 0;
}
int[] dp = new int[s.length() + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i < dp.length; i++) {
int one_digit = s.charAt(i - 1) - '0';
if (one_digit > 0 && one_digit <= 9) {
dp[i] += dp[i - 1];
}
int last_digit = s.charAt(i - 2) - '0';
if (last_digit == 0) {
continue;
}
if (last_digit * 10 + one_digit <= 26) {
dp[i] += dp[i - 2];
}
}
return dp[s.length()];
}