[LeetCode]91.Decode Ways

2024-02-19 00:58

文章标签 leetcode decode 91 ways

本文主要是介绍[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;}//ifif(size == 0 || size == 1){return size;}//ifint 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;}//ifelse if(!isValid(s[i-1],s[i]) && isValid(s[i])){res = cur;}//elseelse if(isValid(s[i-1],s[i]) && !isValid(s[i])){res = pre;}//elseelse{return 0;}//elsepre = cur;cur = res;}//forreturn res;}
private:bool isValid(char pre,char cur){if(pre == '1' || (pre == '2' && cur <= '6')){return true;}//ifreturn false;}bool isValid(char cur){if(cur >= '1' && cur <= '9'){return true;}//ifreturn 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;}//ifint 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或者2int 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);}//ifelse{break;}}//if}//for}
};int main(){Solution s;string str("1234");cout<<s.numDecodings(str)<<endl;return 0;
}