您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
golang刷leetcode技巧的解码方法，针对这个问题，这篇文章详细介绍了相对应的分析和解答，希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。
一条包含字母 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)
解题思路：
1，动态规划解决
假设s[0:i-1] 有dp[i]种解码方案
2，状态转移方程
A，如果s[i]='0' 有两种情况
（1）s[i-1]='1' || '2'
这个时候s[i-1] s[i]必须一起解码才行
故 dp[i+1]=dp[i-1]
(2) 其他情况
这时候解码失败
dp［i+1]=0
B，如果s[i-1]='1'，s[i]这一位单独解码或者 和s[i-1]一起解码都可以
dp[i+1]=dp[i]+dp[i-1]
C,如果s[i-1]='2',s[i]>'0' && s[i]<='6' ,同上
dp[i+1]=dp[i]+dp[i-1]
D， 其他情况，只能单独解码
dp[i+1]=dp[i]
3,初始化条件，由于dp[i+1]用到了dp[i]和dp[i-1],所以递增迭代
如果s[0]=='0'直接解码失败，返回0
dp［1］＝1
为了便于计算，我们增加了dp［0］，且初始化值是1
测试用例：
"50926""10""100""110""12""123""0""226""1""123456"
代码实现：
func numDecodings(s string) int {dp:=make([]int,len(s)+1)dp[0]=1if s[0]=='0'{return 0}else{dp[1]=1}for i:=1;i<len(s);i++{if s[i]=='0'{if s[i-1]=='1' || s[i-1]=='2'{dp[i+1]=dp[i-1]}}else{if s[i-1]=='1'{dp[i+1]=dp[i]+dp[i-1]}else if s[i-1]=='2' && s[i]<='6'{dp[i+1]=dp[i]+dp[i-1]}else{dp[i+1]=dp[i]}}}return dp[len(s)]}
代码优化：
由于我们只用到了dp[i]和dp[i-1]俩变量，其他存储是非必须的，所以，可以优化
func numDecodings(s string) int {if s[0]=='0'{return 0}prepre:=1pre:=1cur:=1for i:=1;i<len(s);i++{if s[i]=='0'{if s[i-1]=='1' || s[i-1]=='2'{cur=prepre}else{return 0}}else{if s[i-1]=='1' || ( s[i-1]=='2' && s[i]<='6'){cur=pre+prepre}else{cur=pre}}prepre=prepre=curfmt.Println(cur,pre,prepre)}return cur}
关于golang刷leetcode技巧的解码方法问题的解答就分享到这里了，希望以上内容可以对大家有一定的帮助，如果你还有很多疑惑没有解开，可以关注亿速云行业资讯频道了解更多相关知识。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。