首页 > 代码库 > 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.
算法分析:题意解析:给你一串数字,解码成英文字母。
类似爬楼梯问题,但要加很多限制条件。
定义数组number,number[i]意味着:字符串s[0..i-1]可以有number[i]种解码方法。
回想爬楼梯问题一样,number[i] = number[i-1] + number[i-2]
但不同的是本题有多种限制:
第一: s[i-1]不能是0,如果s[i-1]是0的话,number[i]就只能等于number[i-2]
第二,s[i-2,i-1]中的第一个字符不能是0,而且Integer.parseInt(s.substring(i-2,i))获得的整数必须在0到26之间。
public class DecodeWays { public int numDecodings(String s) { if(s == null || s.length() == 0) { return 0; } if(s.charAt(0) == ‘0‘) { return 0; } //dp[i]代表前i个字符有多少种编码方式 int[] dp = new int[s.length()+1]; dp[0] = 1;//必须初始化为1,例如字符串“10”,初始0出错。 dp[1] = 1; for(int i = 2; i <= s.length(); i ++) { if(s.charAt(i-1) != ‘0‘) { dp[i] = dp[i-1]; } if(s.charAt(i-2) != ‘0‘) { int temp = Integer.parseInt(s.substring(i-2, i)); if(temp >0 && temp <= 26) { dp[i] += dp[i-2]; } } } return dp[s.length()]; }}
Decode Ways,编码方式数量求解。动态规划问题。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。