91. Decode Ways(解码方法)
程序员文章站
2022-07-05 16:19:04
...
这道题的关键在于推导出递推公式,这里我将存储的数组定义为code,字符串为s,code[i]代表前i个字符可解码的数量,即code[i]代表的是s[i-1]及之前字符的总解码数量。
很明显可知code[i]的值与code[i-1]、code[i-2]都有关,当出现诸如s[i-1]='2'且s[i-2]='1'的情况时,code[i]=code[i-1]+code[i-2],否则code[i]=code[i-1]。这里是因为“12”具有“1”+“2”和“12”两种解码方式,因此code[i]=code[i-1](代表s[i-1]='2'的情况,即只解码自己本身的情况)+code[i-2](代表s[i-1]='2'且s[i-2]='1'的情况,即解码自己加上上一个字符解码的情况)。除此之外,还需要注意当s[i-1]='0'时code[i-1]=0的情况,因为s[i-1]='0'时它本身是不能进行解码的,因此code[i-1]必须设为0。
class Solution {
public:
int numDecodings(string s) {
int num = s.length();
if (!num) return 0;
vector<int> code(num + 1, 0);
code[0] = 1;
for (int i = 1; i <= num; i++) {
if (s[i - 1] == '0')
code[i - 1] = 0;
if (s[i - 2] == '1' || s[i - 2] == '2' && s[i - 1] <= '6')
code[i] = code[i - 1] + code[i - 2];
else
code[i] = code[i - 1];
}
return code[num];
}
};