本文主要是介绍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.
示例:
Given encoded message "12"
, it could be decoded as "AB"
(1 2) or "L"
(12).
The number of ways decoding "12"
is 2.
问题分析:
根据题意可知,这是一道动态规划题。dp是状态转移数组,对于s[i - 1] 和 s[i]的不同取值,dp的对应转换过程也不相同。
过程详见代码:
class Solution {
public:int numDecodings(string s) {int len = s.length();if (!len || s[0] == '0') return 0;vector<int> dp(len + 1, 0);dp[1] = 1;dp[0] = 1;for (int i = 1; i < len; i++){int t = (s[i - 1] - '0') * 10 + s[i] - '0';if(!t || t > 26 && t % 10 == 0) return 0;else if(t < 10 || t > 26) dp[i + 1] = dp[i];else if(t == 10 || t == 20) dp[i + 1] = dp[i - 1];else dp[i + 1] = dp[i] + dp[i - 1];}return dp[len];}
};
这篇关于Decode Ways问题及解法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!