华为OD机试 - 过滤组合字符串(python)

题目描述 数字0、1、2、3、4、5、6、7、8、9分别关联 a~z 26个英文字母。

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” 例如7关联”u”,”v”，8关联”x”,”w”，输入一个字符串例如“78”，和一个屏蔽字符串“ux”，那么“78”可以组成多个字符串例如：“ux”，“uw”，“vx”，“vw”，过滤这些完全包含屏蔽字符串的每一个字符的字符串，然后输出剩下的字符串。

输入描述 无

输出描述 无

用例 输入 78 ux 输出 uw vx vw 说明

思路：python的描述会比较简单，这里利用递归思想，先给出所有可能的组合字符串，其次我们利用issubset()方法判断屏蔽字符串是否是可能字符串的子序列，从而剔除包含项，最终得出剩下的字符串

s=[int(x) for x in input()]
block = input()
digit_char_mapping = {
    0: abc,
    1: def,
    2: ghi,
    3: jkl,
    4: mno,
    5: pqr,
    6: st,
    7: uv,
    8: wx,
    9: yz
}

def get_possible_strings(s):
    if not s:
        return []
    first_digit = s[0]
    remaining_digits = s[1:]
    possible_combinations = []
    for char in digit_char_mapping[first_digit]:
        for combination in get_possible_strings(remaining_digits):
            possible_combinations.append(char+combination)
    return possible_combinations

def filter_strings(strings, block_chars):
    for s in strings:
        if set(block_chars).issubset(set(s)):
            strings.remove(s)
    return strings

possible_strings = get_possible_strings(s)
filtered_strings = filter_strings(possible_strings, block)
print(filtered_strings)