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];
}
}
分享到:
相关推荐
js代码-leetcode 91 DEcode Ways
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
大佬的leetcode刷题笔记(c++版本)
vs code LeetCode 插件
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
leetcode中文版
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip
100个leetCode详细解答
LeetCode 刷题汇总1
LeetCode 选讲1
terminal-leetcode, 终端Leetcode是基于终端的Leetcode网站查看器 终端 leetcode终端leetcode是基于终端的leetcode网站查看器。本项目是由 RTV 激发的。 我最近正在学习本地化的反应,以实践我的新知识,并根据这个...
leetcode刷题, 直接用leetcode的分类方式.
该分类为结合《算法导论》的内容,给出Leetcode题目分类。题目主要集中在Leetcode的前400题中,也包括有后面的一些经典值得刷的题。该题目分类按照算法和数据结构排版,即可供单独Leetcode刷题使用,也可以配合学习...
这份文档列出了leetcode几乎所有题目(大约134题)的分类以及难度指示,是刷leetcode的必备良品。现在leetcode总的题目数已经达到150题,所以有部分题目没有包含在这个文档中,但是——足够了。po主刷leetcode的时候...
leetcode高频面试笔试题150+道,亲身总结。
LeetCode面试笔试题
LeetCode 刷题笔记
(C++)LeetCode刷题题解答案
LeetCode 刷题