题目
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.
分析
代码
#include <iostream>
using namespace std;
class Solution {
public:
int numDecodings(string s) {
int size = s.size();
if(s[0] == '0'){
return 0;
}
if(size == 0 || size == 1){
return size;
}
int pre = 1,cur = 1,res;
for(int i = 1;i < size;++i){
if(isValid(s[i-1],s[i]) && isValid(s[i])){
res = pre + cur;
}
else if(!isValid(s[i-1],s[i]) && isValid(s[i])){
res = cur;
}
else if(isValid(s[i-1],s[i]) && !isValid(s[i])){
res = pre;
}
else{
return 0;
}
pre = cur;
cur = res;
}
return res;
}
private:
bool isValid(char pre,char cur){
if(pre == '1' || (pre == '2' && cur <= '6')){
return true;
}
return false;
}
bool isValid(char cur){
if(cur >= '1' && cur <= '9'){
return true;
}
return false;
}
};
int main(){
Solution s;
string str("1202111110");
cout<<s.numDecodings(str)<<endl;
return 0;
}
运行时间
思路2–超时
#include <iostream>
using namespace std;
class Solution {
public:
int numDecodings(string s) {
int size = s.size();
if(size == 0 || size == 1){
return size;
}
int index = -1;
int count = 0;
helper(s,index,count,"");
return count;
}
private:
void helper(string &s,int index,int &count,string word){
int size = s.size();
if(index == size-1){
++count;
cout<<"word->"<<word<<endl;
return;
}
int num = 0;
for(int i = 1;i <= 2;++i){
if(index + i < size){
num = num * 10 + s[index+i] - '0';
if(num <= 26 && num > 0){
word += ('A'+num-1);
helper(s,index+i,count,word);
word.erase(word.size()-1);
}
else{
break;
}
}
}
}
};
int main(){
Solution s;
string str("1234");
cout<<s.numDecodings(str)<<endl;
return 0;
}
<script type="text/javascript">
$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('<ul/>').addClass('pre-numbering').hide();
$(this).addClass('has-numbering').parent().append($numbering);
for (i = 1; i <= lines; i++) {
$numbering.append($('<li/>').text(i));
};
$numbering.fadeIn(1700);
});
});
</script>
分享到:
相关推荐
用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现...
Leetcode 91. 解码方法问题描述算法解法1解法1:def numDecodings(self, s: str) -> int:if 10 <= int
JVM 基础 JAVA 并发 JVM 性能调优 LeetCode 算法 .......
My Solutions to Leetcode Database problems. 我的 Leetcode 数据.zip
Leetcode 题解.pdf
LeetCode 后端.zip
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
Recording personal Java, Python, JavaScript solutions for Leetcode problems. 记录个人 Java, Python, JavaScript 的Leetcode题解.zip
Leetcode101.zip
刷leetcode总结.md
原创:leetcode 111. 二叉树的最小深度记住:最小深度和最大深度方法不同。* Definition for a binary tree node.in
原创:leetcode 107. 二叉树的层次遍历 II【队列】* Definition for a binary tree node.
原创:leetcode 5. 最长回文子串//寻找以i-1,i为中点偶数长度的回文//寻找以i为中心的奇数长度的回文。
原创:leetcode 22.括号生成【回溯】对待这种问题,千万别暴力搜索,那样太笨了。但是这个方法是最容易理解的//回溯法 (后面的括号) 不可以大于 (前面
My Solutions to Leetcode problems. All solutions support C
LeetCode674. 最长连续递增序列674. 最长连续递增序列解题思路:记录每次递增序列的长度,max存储最大长度// 递增序列更新最大长度} else
LeetCode746.使用最小花费爬楼梯746. 使用最小花费爬楼梯解题思路:动态规划当前楼梯最小值=Math.min(前一步最小值,前两步最小值)简化 mi
84. 柱状图中最大的矩形 - 力扣(LeetCode).html