golang刷leetcode 技巧（56）解码方法

golang算法架构leetcode技术php 2020-05-17

143

一条包含字母 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]=1
    if 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:=1
    pre:=1
    cur:=1
    


   for 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=pre
       pre=cur
       fmt.Println(cur,pre,prepre)
   }
   return cur
}

golang 科技新闻

文章转载自golang算法架构leetcode技术php，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

golang刷leetcode 技巧（56）解码方法

评论