leetcode-91-Decode Ways

sihai 发布于2019-07-31 11:05 / 2665人阅读

摘要：经总结，发现当前字符前面的两个字符和一个字符可以拿出来进行分析。当前的数目可以作为和的数目的叠加。所以关系式是其他的特殊情况可以进行特殊处理。需要注意的是如果钱两位是，，则这两位作废，不能计入其他情况的统计，即。

描述

</>复制代码 
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.

</>复制代码 
class Solution:
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        if s[0]=="0" :
            return 0
        elif len(s)==1:
            return 1
        length=len(s)
        dp=[0 for _ in range(length+1)]
        print("dp:==>",dp)
        dp[0]=1
        dp[1]=1
        for i in range(2,length+1):
            l2=int(s[i-2:i])
            l1=int(s[i-1:i])
            if 10",dp)
        out=dp[length]
        return out
if __name__=="__main__":
    st=Solution()
    num="2626"
    num="0"
    num="11"
    num="1"
    num="0"
    num="11"
    num="110"
    out=st.numDecodings(num)
    print(out)

解释：本地是动态规划解决，所以需要分清楚往后叠加增加字符时的数目之间的变化规律。经总结，发现当前字符前面的两个字符和一个字符可以拿出来进行分析。当前的数目可以作为cur_index-2和cur_index-1的数目的叠加。只跟前两个位置的字符处产生的数目有关系。
所以dp关系式是：dp[n]=dp[n-1]+dp[n-2].其他的特殊情况可以进行特殊处理。比如10，20，位数为1的情况。需要注意的是：如果钱两位是10，20，则这两位作废，不能计入其他情况的统计，即 dp[i]=dp[i-2]。

GPU云服务器云服务器 Ways

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/44621.html

【Leetcode】62. 不同路径

摘要：作者码蹄疾毕业于哈尔滨工业大学。机器人试图达到网格的右下角在下图中标记为。问总共有多少条不同的路径例如，上图是一个的网格。有多少可能的路径说明和的值均不超过。示例输入输出解释从左上角开始，总共有条路径可以到达右下角。作者: 码蹄疾毕业于哈尔滨工业大学。小米广告第三代广告引擎的设计者、开发者；负责小米应用商店、日历、开屏广告业务线研发；主导小米广告引擎多个模块重构；关注推荐、搜索、广...

LMou 2019-08-19 11:07 评论0 收藏0
【Leetcode】62. 不同路径

摘要：作者码蹄疾毕业于哈尔滨工业大学。机器人试图达到网格的右下角在下图中标记为。问总共有多少条不同的路径例如，上图是一个的网格。有多少可能的路径说明和的值均不超过。示例输入输出解释从左上角开始，总共有条路径可以到达右下角。作者: 码蹄疾毕业于哈尔滨工业大学。小米广告第三代广告引擎的设计者、开发者；负责小米应用商店、日历、开屏广告业务线研发；主导小米广告引擎多个模块重构；关注推荐、搜索、广...

canopus4u 2019-07-30 17:46 评论0 收藏0
[Leetcode] Decode Ways 解码方式

摘要：最新更新请见动态规划复杂度时间空间思路解码是有规律的，所以我们可以尝试动态规划。如果字符串的第位和第位不能组成有效二位数字，而且第位不是的话，说明我们是在第位的解码方法上继续解码。 Decode Ways 最新更新请见：https://yanjia.me/zh/2019/02/... A message containing letters from A-Z is being en...

animabear 2019-08-14 12:38 评论0 收藏0