博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Decode Ways leetcode
阅读量:6827 次
发布时间:2019-06-26

本文共 2135 字,大约阅读时间需要 7 分钟。

Decode Ways

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.

动态规划

说明

  • state: dp[i]表示前i个字符的总共decode的可能性

  • function:

    1. 如果第i个字符(substring[i-1,i] )可以被decode, dp[i] = dp[i-1]

    2. 如果i-1, i字符(substring[i-2,i-1])可以decode, dp[i] += dp[i-1]

  • inital: dp[0] = 1 因为当长度为2时候找第二种情况就等于dp[0], 此时应该为1而不是0

    dp[1] = 0 或者1 之所以要定义dp[1]因为我们要判定i-2的情况 所以单独列出来

  • return dp[s.length()]

复杂度

时间复杂度O(n), 空间O(n)

代码

public int numDecodings(String s) {    if (s == null || s.length() == 0) {        return 0;    }    int[] dp = new int[s.length() + 1];    dp[0] = 1;    dp[1] = isValid(s.substring(0, 1))? 1 : 0;    for (int i = 2; i <= s.length(); i++) {        if (isValid(s.substring(i - 1, i))) {            dp[i] += dp[i - 1];        }        if (isValid(s.substring(i - 2, i))) {            dp[i] += dp[i - 2];        }    }    return dp[s.length()];}public boolean isValid(String s) {    if (s == null || s.length() == 0) {        return false;    }    if (s.charAt(0) == '0') {        return false;    }    int tem = Integer.parseInt(s);//把string变为int    return tem >= 1 && tem <= 26;}

复杂度

时间复杂度O(n), 空间O(1)

说明

因为每次计算i只用到i之前的两个数

所以这里可以只用一个容量为3的数组, 每次i存在[i%3]对应的位置

代码

public int numDecodings(String s) {    if (s == null || s.length() == 0) {        return 0;    }    int[] dp = new int[3];    dp[0] = 1;    dp[1] = isValid(s.substring(0, 1))? 1 : 0;    for (int i = 2; i <= s.length(); i++) {        dp[i % 3] = 0;        if (isValid(s.substring(i - 1, i))) {            dp[i % 3] += dp[(i - 1) % 3];        }        if (isValid(s.substring(i - 2, i))) {            dp[i % 3] += dp[(i - 2) % 3];        }    }    return dp[s.length() % 3];}public boolean isValid(String s) {    if (s == null || s.length() == 0) {        return false;    }    if (s.charAt(0) == '0') {        return false;    }    int tem = Integer.parseInt(s);//把string变为int    return tem >= 1 && tem <= 26;}

转载地址:http://moykl.baihongyu.com/

你可能感兴趣的文章
Android:Activity与Fragment、Service之间的数据通信
查看>>
深入理解-字符编码ASCII,GB2312,GBK,Unicode,UTF-8
查看>>
Android网络请求练习
查看>>
Halo 博客系统 -0.4.0 发布
查看>>
golang 介绍以及踩坑之四
查看>>
Shiro-集成验证码
查看>>
最全Drawable基础总结
查看>>
(十六)java版电子商务spring cloud分布式微服务b2b2c社交电商-用restTemplate消费服务...
查看>>
小猿圈学习Web前端需要掌握哪些内容?
查看>>
ubuntu 下安装apache+php+mysql
查看>>
eclipse freemarker 插件 地址
查看>>
Kinect for windows中的抓握(Grip)和释放(GripRelease)
查看>>
提高局域网内网速的几个小技巧
查看>>
Left4Dead2's wound
查看>>
Gulp自动压缩、合并文件并在引用文件的地方加hash
查看>>
好产品,从准确把握用户需求开始——卢云飞
查看>>
c++中的双向链表写法,主要实现(增删查改,链表逆置,构造函数,运算符重载,等)...
查看>>
Eclipse 代码格式化
查看>>
android——SharedPreferences存放数据
查看>>
2018-08-07 期 MapReduce模拟实现热销商品排行
查看>>