【华为OD机试真题】字母组合
题目描述
每个数字关联多个字母,关联关系如下:
- 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,
解题思路
要解决这个问题,我们首先需要理解数字与字母之间的映射关系,并生成基于给定数字字符串的所有字母组合。之后,我们需要根据屏蔽字符串过滤这些组合,确保没有任何组合完全包含屏蔽字符串中的所有字符。
具体步骤如下:
- 根据输入的数字字符串,使用字母映射关系生成所有可能的字符组合。
- 过滤这些组合,排除那些包含屏蔽字符串中所有字母的组合。
- 输出剩下的组合。
Python代码解析
from itertools import product
def generate_combinations(digits, block_str):
# 映射关系表
digit_to_chars = {
'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']
}
# 根据输入的数字串获取字符列表
groups = [digit_to_chars[digit] for digit in digits]
# 使用 product 生成所有可能的组合
all_combinations = [''.join(comb) for comb in product(*groups)]
# 筛选组合:不能包含屏蔽字符串中的所有字符
block_set = set(block_str)
valid_combinations = []
for comb in all_combinations:
# 检查当前组合是否包含屏蔽字符串中的所有字符
comb_set = set(comb)
if not block_set.issubset(comb_set):
valid_combinations.append(comb)
return valid_combinations
if __name__ == "__main__":
digits = input().strip()
block_str = input().strip()
combinations = generate_combinations(digits, block_str)
output = ','.join(combinations) + ","
print(output)
#华为OD##华为OD机考##华为OD机试真题##华为OD机试算法题库##华为OD题库#