Dynamic Programming - 91. Decode Ways
Dynamic Programming - 91. Decode Ways
ppxai
发布于 2020-09-23 17:24:46
发布于 2020-09-23 17:24:46
代码可运行
运行总次数：0
代码可运行
91. Decode Ways
A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26Given a non-empty string containing only digits, determine the total number of ways to decode it.
Example 1:
Input: "12" Output: 2 Explanation: It could be decoded as "AB" (1 2) or "L" (12).
Example 2:
Input: "226" Output: 3 Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
思路：
题目意思是有一个只包含数字的字符串，让求出使用给定的映射表来转换，可以有多少种转换的方法，只要是有递归的感觉都可以使用备忘录减少栈空间，优化算法，这是很明显的递归问题，这里使用动态规划求解。状态是：
dp[i] numDecodings(i)的返回值，就是字符串s[i...]的合法转换数量。
代码：
go：
func numDecodings(s string) int {
if s == "" {return 0}
leng := len(s)
if leng == 0 { return 1 }
dp := make([]int, leng+1)
dp[0] = 1;
if s[0] == '0' {
dp[1] = 0
} else {
dp[1] = 1
}
var prev, next uint8
for i := 2; i <= leng; i++ {
next = s[i-1] - '0'
prev = s[i-2] - '0'
sum := prev * 10 + next
if sum == 0 || next == 0 && prev >= 3 {
return 0
} else if next == 0 {
dp[i] = dp[i-2] // 123 12320
} else if prev != 0 && sum <= 26 { // 123 -> 1 + 12
dp[i] = dp[i-1] + dp[i-2]
} else {
dp[i] = dp [i-1] // 1234 = 123
}
}
return dp[leng]
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019年08月15日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
