Leetcode 91. Decode Ways 解码方法(动态规划,字符串处理)

Leetcode 91. Decode Ways 解码方法(动态规划,字符串处理)

题目描述

一条报文包含字母A-Z,使用下面的字母-数字映射进行解码

 'A' -> 1
 'B' -> 2
 ...
 'Z' -> 26

给一串包含数字的加密报文,求有多少种解码方式 举个例子,已知报文"12",它可以解码为AB(1 2),也可以是L (12) 所以解码方式有2种。

测试样例

Input:
"0"
"121212"
"101010"
"1001"
"0101"
Output:
0
13
1
0
0

详细分析

这道题不难,不过corner cases比较多,需要仔细分析。先考虑1212这个例子:(为了表达方便,我们用逗号分隔表示每种解码方式而不用扳手指算,比如1212的一种解码方式为12,12而不用L,L)

1=>

1

12=>

1,2
12

121=>

1,2,1
1,21
12,1

1212=>

1,2,1,2
1,21,2
12,1,2
1,2,12
12,12

到这里就可以总结出规律了,对于1212,其实是两种解码的和:

1,2,1,(2)
1,21,(2)
12,1,(2)
-----------
1,2,(12)
12,(12)

分割线上面是121的解码方式,并在后加以当前下标的2,分割线下面是12的解码方式加以当前下标和前一个下标表示的字符。

可以看出,如果当前字符和前面一个字符可以构成>10 && <=26(不包括20,至于为什么等下说)的字符,那么当前解码方式就是:

dp[i]=dp[i-1]+dp[i-2]

现在考虑一些corner case,如果当前字符是0,那么它并不符合上面的递推公式,考虑2020: 20=>

20

202=>

20,2

2020=>

20,(20)

可以看到2020,由于0不在解码范围内,所以它不能与前一项通过添加后缀的方式构成解码方式,它只是简单等于前两项然后加上后缀20,同理还有10。

按照这种思路,我们可以得出下面的状态转移:

let x = s.substr(i-1,2);
x>0 && x<10:    dp[i]=dp[i-1]
x==10:          dp[i]=dp[i-2]
x>10&&x<20:     dp[i]=dp[i-1]+dp[i-2]
x==20:          dp[i]=dp[i-2]
x>20&&x<=26:    dp[i]=dp[i-1]+dp[i-2]
x>26&&x%10!=0: dp[i]=dp[i-1];
x>26&&x%10==0: return 0

代码实现

代码太烂凑合看吧...

class Solution {
public:
    int numDecodings(string s) {
        if(s.length()==0){
            return 0;
        }
        if(s[0]=='0'){
            return 0;
        }
        if(s.length()==1){
            return 1;
        }
        int dp[100000];
        dp[0]=1;
        std::string ns = s.substr(0,2);
        int t = atoi(ns.c_str());

        if(t>0 && t<10){
            return 0;
        }else if(t==10){
            dp[1]=1;
        }else if(t>10 && t<20){
            dp[1]=2;
        }else if(t==20){
            dp[1]=1;
        }else if(t>20 && t<=26){
            dp[1]=2;
        }else if(t>26 && t%10!=0){
            dp[1]=1;
        }else{
            return 0;
        }
        if(s.length()==2){
            return dp[1];
        }

        for(int i=2;i<s.length();i++){
            std::string tempStr = s.substr(i-1,2);
            int n = atoi(tempStr.c_str());

            if((n>26 && n%10!=0)||(n>0 && n<10)){
                dp[i]=dp[i-1];
            }else if(n>10 && n<=26&& n!=20){
                dp[i]=dp[i-1]+dp[i-2];
            }else if(n==10 || n==20){
                dp[i]=dp[i-2];
            }else if(n==0 || n%10==0){
                return 0;
            }
        }
        return dp[s.length()-1];
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏繁花云

liunx下sed命令的用法

单引号里面,s表示替换,三根斜线中间是替换的样式,特殊字符需要使用反斜线”\”进行转义,但是单引号”‘”是没有办法用反斜线”\”转义的,这时候只要把命令中的单...

8500
来自专栏编程之旅

Swift中的"警卫队"

大半个月没有更新自己的博客了,最近在忙一个新项目时间非常紧张,所以最近的博客更新进度就要稍微放缓一点了。

8910
来自专栏racaljk

go defer (go延迟函数)

Go语言的defer算是一个语言的新特性,至少对比当今主流编程语言如此。根据GO LANGUAGE SPEC的说法:

10130
来自专栏java达人

js的回调函数详解

在Javascript中,函数是第一类对象,这意味着函数可以像对象一样按照第一类管理被使用。既然函数实际上是对象:它们能被“存储”在变量中,能作为函数参数被传递...

38350
来自专栏web前端教室

web前端零基础课-0908*福祥-学习笔记

学了部分js内容后,完成了网站首页部分动态效果(搜索栏、侧边导航条、轮播图),先用最基本的,冗余最多的一步步实现;后面对Js进行了初步的封装,重新构建了Js文件...

9130
来自专栏ml

C plus plus 控制格式

使用这些格式需要声明包含<iomainip> long flags( ) const 返回当前的格式标志。 long flays(long newflag) 设...

22140
来自专栏C++

python笔记:#011#循环

21120
来自专栏老九学堂

C语言这个基础知识,99%的人都了解不全面

说明:这是学C语言最基本的知识点,简单的使用不难, 但是里面的一些细节和原理就值得我们好好推敲了,想要学好C语言或者编程语言的小伙伴,真的可以好好看看哦~

13800
来自专栏iOS122-移动混合开发研究院

【读书笔记】A Swift Tour

素材:A Swift Tour 推荐下载Playground:Download Playground objc 自己较为熟悉,想熟悉下风头正劲的 swift。就...

36880
来自专栏静晴轩

JavaScript 之 this 详解

JavaScript作为一种脚本语言身份的存在,因此被很多人认为是简单易学的。然而情况恰恰相反,JavaScript支持函数式编程、闭包、基于原型的继承等高级功...

46050

扫码关注云+社区

领取腾讯云代金券