首页 > 代码库 > leetcode第一刷_Decode Ways
leetcode第一刷_Decode Ways
这道题还挺难的。递归的思路是好想,不过不出意料的超时了。
dp嘛。想一下i-1的编码加上第i个编码会怎样,如果加上的这个编码不是0,那么这一位可以独立解码,那长为i的解码个数至少是长为i-1的解码个数。还有呢?如果i-1位是1,可以把i-1位和i位同时解码出来,还有呢?如果i-1位是2而i位是0-6中的数字,也可以同时解码这两位编码。满足这个条件的时候,当前长度的解码个数还要加上i-2时的解码个数。
完全可以用一个数组存放过去的结果,但是很明显,当前的结论只与前一个和前前一个结果有关系。只要用三个数分别表示当前的,之前一个的,之前两个的解码个数,就可以了。具体的实现细节如下:
class Solution { public: int numDecodings(string s) { if(s==""||s[0]==‘0‘) return 0; if(s.length() == 1) return 1; int res = 0, res1 = 1, res2 = 1; for(int i=2;i<=s.length();i++){ res = 0; if(s[i-1] != ‘0‘) res += res1; if(s[i-2] == ‘1‘||(s[i-2]==‘2‘ && s[i-1]<‘7‘)) res += res2; res2 = res1; res1 = res; } return res; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。