`
standalone
  • 浏览: 619301 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

[leetcode] Decode ways

阅读更多
http://leetcode.com/onlinejudge#question_91
Decode WaysJun 25 '121292 / 5011
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.


Solution: DP Problem again.

public class Solution {
    public int numDecodings(String s) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(s.length() == 0) return 0;
        int num[] = new int[s.length()];
        
        int n1 = Integer.parseInt(s.substring(0,1));        
        if(n1==0)  return 0;
        if(s.length() == 1) return 1;
        num[0]=1;
        
        int n2 = Integer.parseInt(s.substring(0,2));
        if(n2==10 || n2==20 || (n2>26 && n2%10!=0)) num[1] = 1;
        else if(n2<=26 && n2>=11) num[1] = 2;
        else return 0;
        
        for(int i=2;i<s.length();i++){
            n1 = Integer.parseInt(s.substring(i,i+1));
            n2 = Integer.parseInt(s.substring(i-1,i+1));
            if(n1==0 && n2==0) return 0;
            if(n1 != 0) num[i] += num[i-1];            
            if(n2>=10 && n2 <= 26) num[i] += num[i-2];
        }
        return num[s.length() -1];
    }
}
分享到:
评论

相关推荐

    java-leetcode题解之Decode Ways II.java

    本篇题解针对的是LeetCode中一道经典的字符串处理问题——Decode Ways II(解码方法 II)。这个问题在算法领域具有一定的挑战性,因为它涉及到动态规划(Dynamic Programming, DP)的应用,同时也需要对字符串的遍历...

    java-leetcode题解之Decode Ways.java

    Decode Ways问题是一个典型的动态规划问题,也称为“解码方法”。该问题描述如下:给定一个只包含数字的字符串,需要通过以下规则将数字编码为字母:'1' 对应 'A','2' 对应 'B',依此类推,'26' 对应 'Z'。同时,...

    js代码-leetcode 91 DEcode Ways

    "DEcode Ways"是LeetCode中的第91题,它涉及到字符串处理和动态规划的算法知识。下面将详细讨论这个题目以及如何使用JavaScript来解决它。 解题思路: 问题描述:给定一个只包含大写字母的非空字符串s,已知每个...

    c语言-leetcode题解之0091-decode-ways.zip

    本压缩包文件名为“c语言-leetcode题解之0091-decode-ways.zip”,它聚焦于解决LeetCode上的一个特定问题——“0091. Decode Ways”。这个题目的核心是关于字符串解码,要求编写一个C语言函数,能够将输入的一个仅...

    python-leetcode题解之091-Decode-Ways

    在探讨如何解决LeetCode上的“Decode Ways”这一问题时,我们首先需要理解题目的基本要求。这个问题要求我们给出一个从1到26的编码系统,其中每个数字代表一个字母,但26代表'Z'。给定一个数字串,我们的任务是计算...

    js-leetcode题解之91-decode-ways.js

    在探讨JavaScript中解决LeetCode上编号为91的“解码方法数”的问题时,我们首先需要了解该问题的具体内容和相关的算法背景。编号91的问题是:一个仅包含数字的字符串能否被解码为字母组合,这里的解码规则是:'1'...

    php-leetcode题解之解码方法.zip

    例如,著名的“解码方法”问题(Decode Ways)就要求计算给定的数字编码有多少种可能的解码方式,这需要对动态规划有深入的理解。 在解决LeetCode的解码问题时,关键在于理解编码的逻辑,然后选择合适的数据结构和...

    leetcode分类-LeetCode:力码

    leetcode 分类 LeetCode Progress 128/154 Other Solutions C++,有详细思路解释 ...Decode Ways Palindrome Partitioning II Maximal Rectangle ###Recursion N-Queens N-Queens II Balanced Binary Tree Binar

    leetcode怎么计算空间复杂度是指-LeetCode-Solution:我的第一个LeetCode解决方案

    leetcode怎么计算空间复杂度是指 LeetCode-Solution my first solution of LeetCode 2015-5-7 Problem 95,98(80 ...我经常在递归的结束地方忘记return!...091:Decode Ways 简单的一维DP,用额外数组O(n)即可。 139,1

    gasstationleetcode-leetcode:LeetcodeOJ解决方案

    leetcode 【演示记录】 报告 展示 2017/03/06 1.二和,167.二和二 2107/03/06 15.3 总和,16.3 总和最近,18.4 总和,11.最多水的容器 2017/03/09 62.Unique Paths, 63.Unique Paths II, 64.Minimum Path Sum 2017/...

    扩展矩阵leetcode-interview-algorithm:面试算法

    扩展矩阵leetcode interview-algorithm leetCode 待解决 上楼梯问题 how many ways to decode this message @leetCode 91

    javalruleetcode-learn-algorithms::laptop:Java实现的各种算法题解

    Ways](./leetcode/动态规划-Decode Ways.java) [动态规划-Distinct Subsequences](./leetcode/动态规划-Distinct Subsequences.java) [动态规划-Longest Valid Parentheses](./leetcode/动态规划-Longest Valid ...

Global site tag (gtag.js) - Google Analytics