# [LeetCode]91.Decode Ways

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.

/*---------------------------------------
*   日期：2015-06-23
*   作者：SJF0115
*   题目: 91.Decode Ways
*   网址：https://leetcode.com/problems/decode-ways/
*   结果：AC
*   来源：LeetCode
*   博客：
-----------------------------------------*/
#include <iostream>
using namespace std;

class Solution {
public:
int numDecodings(string s) {
int size = s.size();
if(s[0] == '0'){
return 0;
}//if
if(size == 0 || size == 1){
return size;
}//if
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;
}//if
else if(!isValid(s[i-1],s[i]) && isValid(s[i])){
res = cur;
}//else
else if(isValid(s[i-1],s[i]) && !isValid(s[i])){
res = pre;
}//else
else{
return 0;
}//else
pre = cur;
cur = res;
}//for
return res;
}
private:
bool isValid(char pre,char cur){
if(pre == '1' || (pre == '2' && cur <= '6')){
return true;
}//if
return false;
}
bool isValid(char cur){
if(cur >= '1' && cur <= '9'){
return true;
}//if
return false;
}
};

int main(){
Solution s;
string str("1202111110");
cout<<s.numDecodings(str)<<endl;
return 0;
}


/*---------------------------------------
*   日期：2015-06-21
*   作者：SJF0115
*   题目: 91.Decode Ways
*   网址：https://leetcode.com/problems/decode-ways/
*   结果：超时
*   来源：LeetCode
*   博客：
-----------------------------------------*/
#include <iostream>
using namespace std;

class Solution {
public:
int numDecodings(string s) {
int size = s.size();
if(size == 0 || size == 1){
return size;
}//if
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;
}//if
// 步长为1或者2
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);
}//if
else{
break;
}
}//if
}//for
}
};

int main(){
Solution s;
string str("1234");
cout<<s.numDecodings(str)<<endl;
return 0;
}


LeetCode 91. Decode Ways

53 0
LeetCode 92 Decode Ways

671 0
LeetCode 91 Decode Ways（编码方式）（*）

955 0
|
1月前
|

【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题-2
【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题
27 2
|
1月前
|

【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题-1
【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题
33 2
|
1月前
|

【LeetCode刷题】二分查找：山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找：山脉数组的峰顶索引、寻找峰值
23 1
|
1月前
|

【LeetCode刷题】滑动窗口解决问题：串联所有单词的子串（困难）、最小覆盖子串（困难）
【LeetCode刷题】滑动窗口解决问题：串联所有单词的子串（困难）、最小覆盖子串（困难）
20 1
|
1月前
|

【LeetCode刷题】滑动窗口解决问题：水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题：水果成篮、找到字符串中所有字母异位词
25 1