[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;
}

运行时间

这里写图片描述

思路2–超时

/*---------------------------------------
*   日期: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
字母A到Z分别和1到26的数字一一对应,给定一串用字符表示的数字,将数字串从不同位置拆开,每一个数字都对应一个字符,如此构成了一个字母字符串. 从不同的位置拆分数字字符串,可以得到不同的字母字符串,问一共有多少种有效的拆分方式.
53 0
LeetCode 91. Decode Ways
LeetCode 92 Decode Ways
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/51339103 ...
671 0
LeetCode 91 Decode Ways(编码方式)(*)
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/51340198 ...
955 0
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1月前
|
索引
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
|
1月前
|
算法
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
|
1月前
|
算法 容器
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词