首页 > 代码库 > Decode Ways
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.
分析：比较容易想到的方法是递归，decode有两种方式，一种是对当前一个数字decode，另一种是如果当前开始的两个数字小于等于26我们可以对开始的两个数字decode，然后再递归的对剩下的数字序列decode。但这种方法超时，代码如下：
class Solution {public: int numDecodings(string s) { return getNumDecodings(s, 0); } int getNumDecodings(string s, int start){ if(start == s.length()) return 0; if(start == s.length()-1) return 1; return (atoi(s.substr(start,2).c_str()) <= 26)?getNumDecodings(s,start+1) + getNumDecodings(s,start+2):getNumDecodings(s,start+1); }};
仔细考虑一下，该题可以用动态规划解，一个字符编码s的解码种类数可以通过s[0..s.length()-2]和s[0..s.length()-3]的解码种类数计算。所以下面的关键在于如果确定递推式。
如果s[cur]是0，我们需要特别处理，只有当s[cur-1]是大于0小于3时，s[0..cur]的解码数等于s[0..cur-2]，也就是说不能有preceding的0. 动态规划的时间复杂度是O(n)，空间复杂度也是O(n).
class Solution {public: int numDecodings(string s) { if(s.length() == 0) return 0; vector<int> records(s.length()+1,1); for(int i = 0; i < s.length(); i++){ if(s[i] == ‘0‘){ if(i == 0 || s[i-1] == ‘0‘ || s[i-1] >= ‘3‘) return 0; records[i+1] = records[i-1]; } else{ records[i+1] = records[i]; if(i > 0 && s[i-1] != ‘0‘ && (atoi(s.substr(i-1,2).c_str()) <= 26)) records[i+1] += records[i-1]; } } return records[s.length()]; }};
Decode Ways
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。