问题描述
用数字126代表大写字母AZ，输入一个非空的数字字符串，要求输出这个数字字符串转成大写字母时有多少种转换的方式。题目链接：**点我**
样例输入输出
输入：”12”
输出：2
输入：”226”
输出：3
输入：”302”
输出：0
问题解法
此题可以转换为已知一个字符串的的转换方式数，求当加入一个新的字符组成一个新的字符串时的转换方式数。这很明显可以使用递归或动态规划解法。此处用动态规划进行求解。假设用 f(n) 表示前 n 个数的转换方式数，则可以得出以下的动态规划方程
- 如果第 n 个数是0
- 如果第 n - 1个数是1或者2，则 f(n) = f(n - 2)，因为只能把最后两个数一起转换
- 否则，f(n) = 0，此时没有任何转换方式满足
- 如果第 n 个数不是 0，第 n - 1个数是 0，则 f(n) = f(n - 1)，因为最后一个数必须单独进行转换
- 如果第 n 个数和第 n - 1个数都不是0
- 如果第 n - 1个数和第n - 2个数构成的数字小于等于26，则 f(n) = f(n - 1) + f(n - 2)，因为此时可以将最后两个数一起转换，也可以将最后一个数单独转换，如果是最后两个数一起转换，则转换方式有 f(n - 2)，如果是将最后一个数单独转换，则转换方式有 f(n - 1)
- 如果第 n - 1个数和第n - 2个数构成的数字大于26，则 f(n) = f(n - 1)，因为此时只能将最后一个数单独转换
初始化时，f(0) = 1, f(1) = 0(当前位是0，前一位大于2)，或 f(1) = 1(当前位是0，前一位是1或2，或当前位不是0且与前一位构成数字大于26)，或 f(1) = 2(当前位不是0，且与前一位构成的数字小于等于26)
代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| class Solution
{
public int numDecodings(String s)
{
int size = s.length();
if (size == 0 || s.startsWith("0"))
{
return 0;
}
if (size == 1)
{
return 1;
}
int[] a = new int[size];
a[0] = 1;
a[1] = 1;
if (s.charAt(1) == '0' && s.charAt(0) != '1' && s.charAt(0) != '2')
{
a[1] = 0;
}
else if (Integer.parseInt(s.substring(0, 2)) <= 26 && s.charAt(1) != '0')
{
a[1] = 2;
}
for (int i = 2; i < size; i++)
{
if (s.charAt(i) == '0')
{
if (s.charAt(i - 1) == '1' || s.charAt(i - 1) == '2')
{
a[i] = a[i - 2];
}
else
{
a[i] = 0;
}
}
else if (s.charAt(i - 1) == '0')
{
a[i] = a[i - 1];
}
else if (Integer.parseInt(s.substring(i - 1, i + 1)) <= 26)
{
a[i] = a[i - 1] + a[i - 2];
}
else
{
a[i] = a[i - 1];
}
}
return a[size - 1];
}
}
|