首页 > 代码库 > 91. Decode Ways
91. 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.
分析:需要注意的是,如果序列中有不能匹配的0,那么解码方法是0,比如序列012 、100(第二个0可以和1组成10,第三个0不能匹配)。递归的解法很容易,但是大集合会超时。转换成动态规划的方法,假设dp[i]表示序列s[0...i-1]的解码数目,动态规划方程如下:
- 初始条件:dp[0] = 1, dp[1] = (s[0] == ‘0‘) ? 0 : 1
- dp[i] = ( s[i-1] == 0 ? 0 : dp[i-1] ) + ( s[i-2,i-1]可以表示字母 ? dp[i-2] : 0 ), 其中第一个分量是把s[0...i-1]末尾一个数字当做一个字母来考虑,第二个分量是把s[0...i-1]末尾两个数字当做一个字母来考虑
代码如下:
class Solution { public: int numDecodings(string s) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. //注意处理字符串中字符为0的情况 int len = s.size(); if(len == 0)return 0; int dp[len+1];//dp[i]表示s[0...i-1]的解码方法数目 dp[0] = 1; if(s[0] != ‘0‘)dp[1] = 1; else dp[1] = 0; for(int i = 2; i <= len; i++) { if(s[i-1] != ‘0‘) dp[i] = dp[i-1]; else dp[i] = 0; if(s[i-2] == ‘1‘ || (s[i-2] == ‘2‘ && s[i-1] <= ‘6‘)) dp[i] += dp[i-2]; } return dp[len]; } };
2、带标记的递归
public class Solution { public int numDecodings(String s) { if(s == null || s.isEmpty()) return 0; return findTotal(s,0); } Map<Integer,Integer> result = new HashMap<>(); public int findTotal(String s,int index){ if(index == s.length()){ return 1; } if(s.charAt(index) == ‘0‘){ return 0; } int dou; Integer temp1 = result.get(index+1); if(temp1 == null){ temp1 = findTotal(s,index+1); result.put(index+1,temp1); } if(index + 1 < s.length() && (dou = Integer.valueOf(s.substring(index,index+2)))<= 26&& dou > 0){ // 可以跳两步, Integer temp2 = result.get(index+2); if(temp2 == null){ temp2 = findTotal(s,index+2); result.put(index+2,temp1); } return temp1 + temp2; }else{ // 只能跳一步 return temp1; } }}
91. Decode Ways
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。