资讯专栏INFORMATION COLUMN

91. Decode Ways

macg0406 / 1740人阅读

A message containing letters from A-Z is being encoded to numbers using the following
"A" -> 1
"B" -> 2
...
"Z" -> 26
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.
// O(n) time, O(1) space
public class Solution {
    public int numDecodings(String s) {
        if(s.length() == 0) return 0;
        // i is decided by i+1, i+2
        int pre = 27, digit, first = 1, second = 1, res = 0;
        for(int i=s.length() -1; i>=0; i--) {
            digit = s.charAt(i) - "0";
            if(digit == 0) res = 0;
            else res = first + (digit*10 + pre <= 26 ? second : 0);
            second = first; first = res; pre = digit;
        }
        
        return res;
    }
}
/*  O(n) time, substring takes O(n), O(n) space
public class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        if(n == 0) return 0;
        int[] memo = new int[n+1];  // ways to decode after this position
        memo[n] = 1;                // nothing to decode
        memo[n-1] = s.charAt(n-1) == "0" ? 0 : 1;
        
        for(int i=n-2; i>=0; i--) {
            if(s.charAt(i) == "0") continue;
            memo[i] = (Integer.parseInt(s.substring(i, i+2)) <= 26) ? memo[i+1] + memo[i+2] : memo[i+1];  
        }
        
        return memo[0];
    }
}
*/

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

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

相关文章

  • leetcode-91-Decode Ways

    摘要:经总结,发现当前字符前面的两个字符和一个字符可以拿出来进行分析。当前的数目可以作为和的数目的叠加。所以关系式是其他的特殊情况可以进行特殊处理。需要注意的是如果钱两位是,,则这两位作废,不能计入其他情况的统计,即。 描述 A message containing letters from A-Z is being encoded to numbersusing the following...

    sihai 评论0 收藏0
  • [Leetcode] Decode Ways 解码方式

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

    animabear 评论0 收藏0
  • [LintCode/LeetCode] Decode Ways [String to Integer

    摘要:用将子字符串转化为,参见和的区别然后用动规方法表示字符串的前位到包含方法的个数。最后返回对应字符串末位的动规结果。 Problem A message containing letters from A-Z is being encoded to numbers using the following mapping: A -> 1 B -> 2 ... Z -> 26 Given ...

    andong777 评论0 收藏0
  • 2019 “掘安杯” write up

    摘要:前言肝了一天,最后打了第三,记录下。同一样,它也将输入的字符串或数据编码成全是码的可打印字符串。 前言 肝了一天,最后打了第三,记录下。我逆向真的好菜啊~~~~ Reverse baby_reverse 加密函数如下 int __fastcall encode(const char *a1, __int64 a2) { char v3[32]; // [rsp+10h] [rbp-...

    LiuRhoRamen 评论0 收藏0
  • 2019 “掘安杯” write up

    摘要:前言肝了一天,最后打了第三,记录下。同一样,它也将输入的字符串或数据编码成全是码的可打印字符串。 前言 肝了一天,最后打了第三,记录下。我逆向真的好菜啊~~~~ Reverse baby_reverse 加密函数如下 int __fastcall encode(const char *a1, __int64 a2) { char v3[32]; // [rsp+10h] [rbp-...

    Jochen 评论0 收藏0

发表评论

0条评论

macg0406

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<