首页 > 代码库 > (每日算法)LeetCode --- Decode Ways
(每日算法)LeetCode --- Decode Ways
A message containing letters from A-Z
is being encoded to numbers using the following mapping:
‘A‘ -> 1 ‘B‘ -> 2 ... ‘Z‘ -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message "12"
, it could be decoded as "AB"
(1 2) or "L"
(12).
The number of ways decoding "12"
is 2.
/*每次对于当前的字符判断是否属于1-9(0肯定不行,因为0不在1-26中),如果属于,那么当前的字符可以被decode,并且和f[n-1]组合,f[n] += f[n-1] 然后对于当前字符和前一个字符组成的字符串判断是否属于10-26,如果属于,那么这两个字符可以被decode,并且和f[n-2]组合,f[n] += f[n-2] */ class Solution { public: int numDecodings(string s) { int * a; a = new int[s.size()+1]; memset(a,0,(s.size()+1)*sizeof(int)); if(s.size() == 0) return 0; a[0] = 1; for(int i = 1; i <= s.size(); i++) { if(s[i-1] != '0') a[i] += a[i-1]; if(i -2 >= 0 && s[i-1] - '0' + 10 * (s[i-2] - '0') <= 26 && s[i-1] - '0' + 10 * (s[i-2] - '0') >= 10) a[i] += a[i-2]; } return a[s.size()]; } };
(每日算法)LeetCode --- Decode Ways
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。