密码破译

[编程题]密码破译

热度指数：2668 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

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

输入描述:

多行数据，每行为一个数字串。
保证数字串的总长度不超过1000，每行数据的答案至少有1个且不超过1000个。

输出描述:

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

示例1

输入

1
12
123

输出

a
ab l
abc aw lc

算法知识视频讲解

Python

sky游荡

还好，就是0这个东西，让我找了半天bug，最后输出格式没调好。核心代码就dfs哪里。

while True:
    try:
        ss = input()
        def dfs(ss,tmp,ts,ans):
            if not ss:
                ans.append(ts)
                return ans   
            for i in range(1,3):        
                if len(ss)-i>=0:
                    tmp = ss[0:i]            
                    if int(tmp)<=26 and int(tmp)>0 and tmp[0]!='0' :                      
                        ts= ts+'*'+tmp            
                        dfs(ss[i:],tmp,ts,ans)                
                        ts = ts[:-2]
            return ans
        ans = dfs(ss,'','',[])
        last =[]
        for d in ans:
            s = d.replace('*',' ').strip()
            nums = s.split()
            res = []
            for i in range(len(nums)):
                res.append(chr(int(nums[i])-1+ord('a')))
            last.append(res)
        ans =[]    
        for d in last:
            ans.append(''.join(d))
        print(' '.join(ans))
    except:
        break

编辑于 2020-04-25 02:11:37 回复(0)

Python

贾志统

def func(nn, res, lst):
    if len(nn) == 0:
        if res not in lst:
            lst.append(res)
            return
    for i in range(len(nn)):
        if nn[i] == "1" and i+1 < len(nn):
            if nn[i+1] == "0":
                func(nn[i+2:], res+num_to_char(nn[i:i+2]), lst)
                return
            else:
                if i+2 < len(nn) and nn[i+2] == "0":
                    func(nn[i+1:], res+num_to_char(nn[i]), lst)
                    return
                else:
                    func(nn[i+1:], res+num_to_char(nn[i]), lst)
                    func(nn[i+2:], res+num_to_char(nn[i:i+2]), lst)
                    return
        elif nn[i] == "2" and i+1<len(nn) and int(nn[i+1]) <= 6:
            if nn[i+1] == "0":
                func(nn[i+2:], res+num_to_char(nn[i:i+2]), lst)
                return
            else:
                if i+2<len(nn) and nn[i+2] == "0":
                    func(nn[i+1:], res+num_to_char(nn[i]), lst)
                    return
                else:
                    func(nn[i+1:], res+num_to_char(nn[i]), lst)
                    func(nn[i+2:], res+num_to_char(nn[i:i+2]), lst)
                    return
        else:
            res += num_to_char(nn[i])
    if res not in lst:
        lst.append(res)
        
            

def num_to_char(num_str):
    return chr(int(num_str) + 96)
while True:
    try:
        nn = input()
        res = ""
        lst = []
        func(nn, res, lst)
        lst.sort()
        for per_str in lst:
            print(per_str, end=" ")
        print()
    except:
        break

发表于 2019-09-08 12:55:01 回复(0)

Python

ElonB

""""
递归求解，一种变式DFS
对存在'0'的情况特殊处理
"""
import sys


def dfs(s, temp, ans):
    if not s:
        ans.append(''.join(temp))
        return
    if (len(s) >= 2 and s[1] != '0') or len(s) == 1:
        dfs(s[1:], temp + (chr(int(s[0]) + ord('a') - 1),), ans)
    if (len(s) >= 3 and s[2] != '0' or len(s) == 2) and int(s[:2]) <= 26:
        dfs(s[2:], temp + (chr(int(s[:2]) + ord('a') - 1),), ans)


if __name__ == "__main__":
    for line in sys.stdin:
        s = line.strip()
        ans = []
        dfs(s, tuple(), ans)
        print(' '.join(ans))

发表于 2019-07-13 21:44:07 回复(0)