LeetCode 91. Decode Ways

题目链接 Decode Ways



斐波那契数列的变形,难度比斐波那契数列提升了不少,主要就是会有一些限制条件,搞清楚就可以.递归思路击败9.52%,循环思路击败91.16%

递归思路



我一开始用递归的方式写的

递归结束条件是s 的长度为1,2

n 的长度如果是1, 返回1,

n 的长度如果是2, 判断一下是否>26,如果>26返回1,否则返回2

递归结束条件还有一个就是看 s 的开头是不是’0’,如果是0直接返回0

递归过程是

每次取 s 的前两个字符

如果>26则结果为 numDecodings(s.substring(1))

否则,结果为numDecodings(s.substring(1)) ~ numDecodings(s.substring(2))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static int numDecodings(String s) {
if (s.startsWith("0")) {
return 0;
} else if (s.length() == 1) {
return 1;
} else if (s.length() == 2) {
int a = Integer.parseInt(s);
if (a > 26) {
return numDecodings(s.substring(1));
}
if (s.charAt(1) == '0') {
return 1;
}
return 2;
}
String head = s.substring(0, 2);
if (Integer.parseInt(head) > 26) {
return numDecodings(s.substring(1));
} else {
return numDecodings(s.substring(1)) + numDecodings(s.substring(2));
}
}

循环思路



先判断整个字符串开头是否为0,如果是0,直接 gg

然后循环从第二个字符开始(下标为1的),

分几种情况

第一种,当前字符是0,这意味着必须要结合前一个字符组成一个两个字符数字的映射,那如果这时候前一个字符也是0或者前一个字符>2,那就直接 gg

第二种,当前字符在第一种基础上仍然为0(说明前一个字符必然是1或者2),此时 result[current_index] = result[current_index - 2] = result[previous_index - 1]

第三种,前一个字符为0,或者前一个字符和当前字符组合> 26,这意味着增加后一个字符的字符串的映射方法种树没有发生改变

result[current_index] = result[previous_index]

第四种, 除了上面3种以外的情况

此时result[current_index] = result[current_index - 1] + result[current_index - 2]

以上使用的current_index 都是相对于 result 数组

等下代码里要注意 result 数组的长度和 s 的长度是不一样的,下标也会相差1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static int numDecodings(String s) {
int[] result = new int[s.length() + 1];
if (s.length() == 0 || s.charAt(0) == '0') {
return 0;
}
result[0] = 1;
result[1] = 1;
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == '0' && s.charAt(i - 1) == '0' || s.charAt(i) == '0' && s.charAt(i - 1) > '2') {
return 0;
}
if (s.charAt(i - 1) == '0' || (s.charAt(i - 1) - '0') * 10 + (s.charAt(i) - '0') > 26) {
result[i + 1] = result[i];
} else if (s.charAt(i) == '0') {
result[i + 1] = result[i - 1];
} else if (s.charAt(i) != '0' && s.charAt(i - 1) != '0') {
result[i + 1] = result[i] + result[i - 1];
}
}
return result[s.length()];
}
月月说要给我打赏,就还是放了二维码,😝