题目地址:
https://leetcode.com/problems/decode-ways-ii/
给定一个只含数字的长
n
n
n的字符串
s
s
s,再给定一个对应规则,每个大写字母ch
可以对应一个数字ch - 'A' + 1
。问该
s
s
s有多少种不同的解码方式。
s
s
s中可能含有'*'
,这个符号可以对应除了
0
0
0以外的任意一位数。答案模
1
0
9
+
7
10^9+7
109+7后返回。
思路是动态规划。设 f [ i ] f[i] f[i]是 s s s的长 i i i的前缀的解码方式数,那么可以按照最后一位(或者两位)是解码成什么字母来分类进行累加。代码如下:
public class Solution {
public int numDecodings(String s) {
int MOD = (int) (1E9 + 7);
int[] dp = new int[Math.max(2, s.length() + 1)];
dp[0] = 1;
dp[1] = s.charAt(0) == '*' ? 9 : s.charAt(0) == '0' ? 0 : 1;
for (int i = 2; i <= s.length(); i++) {
// 枚举s的长i前缀的末尾可以解码为哪个大写字母
for (int j = 1; j <= 26; j++) {
char ch0 = s.charAt(i - 1);
// 如果是要解码为A到I,那么最后一个数字得单独解码
if (j <= 9) {
if (ch0 == '*' || ch0 == '0' + j) {
dp[i] += dp[i - 1];
}
} else {
// 否则最后两个数字得一起解码
char ch1 = s.charAt(i - 2);
int i0 = j % 10, i1 = j / 10;
if ((ch1 == '*' || ch1 == i1 + '0') && ((ch0 == '*' && i0 != 0) || ch0 == i0 + '0')) {
dp[i] += dp[i - 2];
}
}
dp[i] %= MOD;
}
}
return dp[s.length()];
}
}
时空复杂度 O ( n ) O(n) O(n)。