numToAlpha

数字字符串转换成字母组合的种数

给定一个字符串str,str全部由数字字符组成，如果str中某一个或某相邻两个字符组成的子串值1~26之间，则这个子串可以转换为一个字母。规定"1"转换为"A",“2”转换为"B",“3”转换为"c","26"转换为"Z"。写一个函数，求str有多少种不同的转换结果。

#include <string>
#include <iostream>

using namespace std;


//recursive
int dfs(string &str, int pos){
    if(pos == str.size())    return 1;
    if(str[pos] == '0')    return 0;

    int res = dfs(str, pos + 1);

    if(pos + 1 < str.size() && (str[pos] - '0')*10 + str[pos + 1] - '0' < 27){
        res += dfs(str, pos + 2);
    }

    return res;

}

int solve(string &s){
    if(s.empty())    return 0;

    return dfs(s, 0);
}


//dp算法
int dp(string &s){
    int n = s.size();

    if(n <= 0)    return 0;

    int prev1 = s[n - 1] == '0'?0:1;
    int prev2 = 1;

    int tmp = 0;

    for(int i = n - 2; i >= 0; i--){
        if(s[i] == '0'){
            prev2 = prev1;
            prev1 = 0;
        }else{
            int tmp = prev1;
            if((s[i] - '0')* 10 + s[i + 1] - '0' < 27){
                prev1 += prev2;
            }
            prev2 = tmp;
        }

    }
}

int main(){
    string test = "1111";

    cout<<solve(test)<<endl;

    return 0;
}