小米2018校招在线考试-编程题三

发表于 | 分类于 ，

题目 密码破译

描述

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

输入

多行数据，每行为一个数字串。

输出

多行数据，每行对应输出通过数字串破译得到的所有字符串，
并按照字符串顺序排列，字符串之间用单个空格分隔。
每行开头和结尾不允许有多余的空格。

Example

Input

1
12
123

Output

a
ab l
abc aw lc

题解

深度优先搜索

  • 神搜+剪枝
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>

using namespace std;

string s;
int count;

void dfs(string &str,int i)
{
    if(i==str.length())
    {
        if(count)cout<<" ";
        cout<<s;
        ++count;
        return ;
    }
    int val;
    val=str[i]-'0';
    s.push_back((char)(val+'a'-1));
    dfs(str,i+1);
    s.pop_back();
    if(i+1<str.length())
    {
        val=val*10+str[i+1]-'0';
        if(val<=26)
        {
            s.push_back((char)(val+'a'-1));
            dfs(str,i+2);
            s.pop_back();
        }
    }
}

int main()
{
    string str;
    while(cin>>str)
    {
        count=0;
        dfs(str,0);
        cout<<endl;
    }
}