leetcode-91-Decode Ways

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

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

描述

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