题目:
难度:Middle
相关话题:字符串
、动态规划
一条包含字母 A-Z
的消息通过以下方式进行了编码:
'A' -> 1
'B' -> 2
...
'Z' -> 26
给定一个只包含数字的非空 字符串,请计算解码方法的总数。
示例 1:
输入: "12"
输出: 2
解释:它可以解码为 "AB"(1 2)或者 "L"(12)。
示例2:
输入: "226"
输出: 3
解释:它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
思路:
DP,dp[i+1]
为当前索引i
以及之前的字符串有多少种组合,
那么,如果存在一个i
(i>0),那么dp[i+1]=s[i]的组合*dp[i] + (s[i-1],s[i])的组合*dp[i-1]
。
例如:[1,3,6,2,1,2]
:
当i
为2
,对应的s[i]
为6
,那么dp[i+1]
就是(6的组合 * [1,3]的组合) + ([3,6]的组合 * [1]的组合)
。
如果索引i
为1
,那么前面只有1位数,因此我们初始默认dp[0]=1
。
最后就是组合的算法,1位数的组合计算就是除了输入为"0"
返回0
,其他都可以返回1
。
2位数的组合计算,需要判断这个2位数是否在[10,26]
之内,在则返回1
,不在的返回0
; 如果一个2位数是07
,也是同样返回0
,这里不能当做1位数来计算,否则会重复。
/**
* @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍:一个致力于帮助开发者用代码改变世界为使命的平台,每天都可以在这里找到技术世界的头条内容
* @param {string} s
* @return {number}
*/
var numDecodings = function(s) {
let dp=[]
dp[0]=1
dp[1]=s[0]==="0" ? 0 : 1
for(let i=1;i<s.length;i++){
dp[i+1]=calc1(s[i])*dp[i]+calc2(s[i-1],s[i])*dp[i-1]
}
return dp[dp.length-1]
function calc1(s){
if(s==="0")return 0
else return 1
}
function calc2(s1,s2){
let n=+(s1+s2)
if(n<=26 && n>=10){
return 1
}else{
return 0
}
}
};
扩展阅读: