用c++写出要解码已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法)。例如,"11106" 可以映射为: "AAJF",将消息分组为 (1 1 10 6) "KJF",将消息分组为 (11 10 6) 但是,消息不能分组为 (1 11 06) ,因为 "06" 不能映射为 "F" ,这是由于 "6" 和 "06" 在映射中并不等价。 给Jim一个只含数字的非空字符串s,请计算并返回解码方法的总数的完整程序。题目数据保证答案肯定是一个32位的整数,并能在DEV中运行运行
时间: 2023-07-16 17:14:22 浏览: 107
以下是使用动态规划的 C++ 代码实现:
```cpp
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int numDecodings(string s) {
int n = s.size();
if (n == 0 || s[0] == '0') return 0;
vector<int> dp(n+1);
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
// Check if single digit is valid
if (s[i-1] != '0') {
dp[i] = dp[i-1];
}
// Check if two digits is valid
int twoDigits = stoi(s.substr(i-2, 2));
if (twoDigits >= 10 && twoDigits <= 26) {
dp[i] += dp[i-2];
}
}
return dp[n];
}
int main() {
string s = "11106";
cout << numDecodings(s) << endl;
return 0;
}
```
其中,dp[i] 表示字符串前 i 个字符的解码方法总数。我们需要考虑当前字符和前一个字符是否能够组成有效的两位数,以及当前字符是否能够组成有效的单个数字。如果可以,我们将解码方法总数加上 dp[i-2] 或 dp[i-1]。最后返回 dp[n] 即可。
阅读全文