LeetCode 91 - Decode Ways

作者 QIFAN 日期 2017-01-05
LeetCode 91 - Decode Ways

原题链接: 91. Decode Ways


题干

假设有一种编码方式将字母按如下方式编码:

'A' -> 1
'B' -> 2
'C' -> 3
...
'Z' -> 26

给定一个编码后只含数字的信息,求共有多少种解码方式。

思路

存在多种解码方式的原因就在于编码不定长。对于每一个数字,它可以自己解码,或与其前一个数字一起解码。核心等式就出来了。

(另:面试的时候可以问一下编码是否一定有效。)

位置 i 的解码方式 = 位置 i - 1 的解码方式 + 位置 i - 2 的解码方式

常规写法就是新建一个数组来存取每个位置的解码方式,空间复杂度 $O(n)$ ,想到我们其实只需要前两位,之前的也用不着,所以干脆就直接用两个变量。空间复杂度变为了 $O(1)$

因为肯定需要遍历一遍,时间复杂度为 $O(n)$ ,不能再少。

这题要非常注意各类特殊情况啊,弄得我够呛。

- '00' 没有这样的解码,返回 0
- '10' 只能按 '10' 解码,等于 i - 2 位解码数量
- '40' 没有这样的解码,返回 0
- '01' 只能是 '0' 与前面的数字解码,'1' 单独解码,等于 i - 1 位的解码数量
- '14' 既能单独各成解码,也能合起来解码,等于位置 i - 1 的解码方式 + 位置 i - 2 的解码方式
- '56' 只能单独各自解码,等于 i - 1 位的解码数量

代码:

public int numDecodings(String s) {
if (s == null || s.length() == 0 || s.charAt(0) == '0') {
return 0;
}
int lastTwoPosWays = 1;
int lastPosWays = 1;
int ways = 1;
if (s.length() == 1) {
return ways;
}
int encode;
for (int pos = 1; pos < s.length(); pos++) {
encode = Integer.parseInt(s.substring(pos - 1, pos + 1));
// '00'
if (encode == 0) {
return 0;
}
if (s.charAt(pos) == '0') {
// '10'
if (encode < 30) {
ways = lastTwoPosWays;
// '50'
} else {
return 0;
}
// '23'
} else if (encode < 10 || encode > 26) {
ways = lastPosWays;
// '34'
} else {
ways = lastPosWays + lastTwoPosWays;
}
lastTwoPosWays = lastPosWays;
lastPosWays = ways;
}
return ways;
}