【华为OD机试2023】字母组合Python

题目描述：

每个数字对应多个字母，对应关系如下： 0：a,b,c    1：d,e,f    2：g,h,i    3：j,k,l    4：m,n,o    5：p,q,r    6：s,t   7：u,v   8：w,x  9：y, z

输入一串数字后，通过数字和字母的对应关系可以得到多个字母字符串（要求按照数字的顺序组合字母字符串）;

屏蔽字符： 屏蔽字符中的所有字母不能同时在输出的字符串出现，如屏蔽字符时abc，则要求字符串中不能同时出现a，b，c，但是允许同时出现a，b；a，c；b，c等；

给定一个数字字符串和一个屏蔽字符串，输出所有可能的字符组合；

例如输入数字字符串78和屏蔽字符串ux，输出结果为uw，vw，vx；数字字符串78，可以得到如下字符串： uw，ux，vw，vx；由于ux是屏蔽字符串，因此排除ux，最终的输出时uw，vw，vx；

输入描述：

第一行输入为一串数字字符串，数字字符串中的数字不允许重复，数字字符串的长度大于0，小于等于5； 第二行输入是屏蔽字符，屏蔽字符的长度一定小于数字字符串的长度，屏蔽字符串中字符不会重复，

输出描述：

输出可能的字符串组合

注：字符串之间使用逗号隔开，最后一个字符串后携带逗号

示例1

输入：

78

ux

输出：

uw,vw,vx,

示例2

输入：

78

x

输出：

uw,vw,

解题思路：

暴力算法的题，DFS和回溯都行。判断屏蔽字是否都在字符串中，可以使用.issubset()方法（是否是xx的子集）

dict={
    '0':['a','b','c'],
    '1':['d','e','f'],
    '2':['g','h','i'],
    '3':['j','k','l'],
    '4':['m','n','o'],
    '5':['p','q','r'],
    '6':['s','t'],
    '7':['u','v'],
    '8':['w','x'],
    '9':['y','z']
}
num=input()
pb=input()
res=[]
path=[]
l=len(num)
def backtracking(res,path):
    m=len(path)
    if m==l:
        res.append(''.join(path))
        return
    for j in dict[num[m]]:
        path.append(j)
        backtracking(res,path)
        path.pop()
backtracking(res,path)
for zuhe in res:
    if set(pb).issubset(zuhe):
        res.remove(zuhe)
print(','.join(res)+',')