91. Decode Ways

macg0406 发布于2019-08-14 18:05 / 1938人阅读

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];
    }
}
*/

云服务器 GPU云服务器 Ways decode json_decode json_decode_null

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

转载请注明本文地址：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 2019-07-31 11:05 评论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
[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 2019-08-14 15:44 评论0 收藏0
2019 “掘安杯” write up

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

Jochen 2019-07-31 10:17 评论0 收藏0