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 java_leetcode题解之Decode Ways.java
java java_leetcode题解之Decode Ways II.java
"DEcode Ways"是LeetCode中的第91题,它涉及到字符串处理和动态规划的算法知识。下面将详细讨论这个题目以及如何使用JavaScript来解决它。 解题思路: 问题描述:给定一个只包含大写字母的非空字符串s,已知每个...
python python_leetcode题解之091_Decode_Ways
c语言基础 c语言_leetcode题解之0091_decode_ways.zip
javascript js_leetcode题解之91-decode-ways.js
例如,著名的“解码方法”问题(Decode Ways)就要求计算给定的数字编码有多少种可能的解码方式,这需要对动态规划有深入的理解。 在解决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 my first solution of LeetCode 2015-5-7 Problem 95,98(80 ...我经常在递归的结束地方忘记return!...091:Decode Ways 简单的一维DP,用额外数组O(n)即可。 139,1
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 待解决 上楼梯问题 how many ways to decode this message @leetCode 91
Ways](./leetcode/动态规划-Decode Ways.java) [动态规划-Distinct Subsequences](./leetcode/动态规划-Distinct Subsequences.java) [动态规划-Longest Valid Parentheses](./leetcode/动态规划-Longest Valid ...