问题描述
按照1-a, 2-b, 3-c, ... ,26-z 的对应关系可以对一串字符串进行编码， 例如 ace 可以编码为 135,
但对于135进行解码却有两种可能，其一是ace, 其二是me, 设计一个算法求解一串加密得到的数字
字符串对应着几种原文的可能性？
例：
输入：
135
输出：
2
输入：
1234
输出：
3
代码实现
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int stringDecode(const string& str) {
int sz = str.size();
vector<int> vec(sz, 1);
if (sz < 2) {
return sz;
}
if (('1' == str[0]) || ('2' == str[1] && '6' >= str[1])) {
vec[1] = 2;
}
for (int i = 2; i < sz; i++) {
vec[i] = vec[i - 1];
int n = str[i] - '0' + (str[i - 1] - '0') * 10;
if (n >= 10 && n <= 26) {
vec[i] += vec[i - 2];
}
}
return vec[sz - 1];
}
int main() {
while (1) {
string str;
cin >> str;
cout << "可能的加密组合为数:" << stringDecode(str) << endl;
}
return 0;
}
结果检验
转载请注明原文地址: https://ju.6miu.com/read-25424.html
