小米服务端岗位编程题第三题代码

我们来做一个简单的密码破译游戏。破译的规则很简单，将数字转换为字母，1转化为a，2转化为b，依此类推，26转化为z。现在输入的密码是一串数字，输出的破译结果是该数字串通过转换规则所能产生的所有字符串。

输入：
1
12
123
输出：

a
ab l
abc aw lc

这题是leetcode 91.Decode Ways原题的改进版，原题只要输出编码数量，此题需要输出所有编码，代码如下：

    #include 
    #include 
    #include 
    #include 
    #include 
    using namespace std;
    const int LOW = 1, HIGH = 26;
    vector> dp;
    void decode(string s)
    {
        vector res;
        int ls = s.size();
        if (ls == 0) return;
        for (int i = 0; i < ls; i++)
        {
            char ch1 = '0', ch2 = '0';
            int d = s[i] - '0';
            if (d >= LOW && d <= HIGH)
            {
                ch1 = 'a' + d - 1;
            }
            if (i > 0 && s[i-1] != '0')
            {
                d += (s[i-1] - '0')*10;
                if (d >= LOW && d <= HIGH)
                {
                    ch2 = 'a' + d - 1;
                }
            }
            if (ch1 != '0')
            {
                if (i > 0)
                {
                    vector t = dp[i-1];
                    for (auto &str : t)
                    {
                        string s1 = str + ch1;
                        dp[i].push_back(s1);
                    }
                }
                else
                {
                    string s1; s1.push_back(ch1);
                    dp[i].push_back(s1);
                }
            }
            if (ch2 != '0')
            {
                if (i > 1)
                {
                    vector t = dp[i-2];
                    for (auto &str : t)
                    {
                        string s1 = str + ch2;
                        dp[i].push_back(s1);
                    }
                }
                else
                {
                    string s1; s1.push_back(ch2);
                    dp[i].push_back(s1);
                }
            }
        }
    }
    int main()
    {
        string s;
        while (cin >> s)
        {
            dp.clear();
            dp.resize(s.size() + 1);
            decode(s);
            vector res = dp[s.size() - 1];
            for (int i = 0; i < res.size(); i++)
                i == res.size() - 1 ? cout << res[i] << endl : cout << res[i] << " ";
        }
        return 0;
    }