字母组合/过滤组合字符串

题目描述

每个数字关联多个字母, 关联关系如下:

• 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 permutations

def main():
    # 读取输入
    # 建立数字到字母的映射关系
    # 就可以得到输入数字所有可能的字符串
    # 然后去掉被屏蔽的字符串, 就得到了结果
    num_str = input()
    assert 0 < len(num_str) < 5
    filter_str = input()

    num_digits = list(map(int, num_str))
    digit_mapping = ["abc", "def", "ghi", "jkl", "mno", "pqr", "st", "uv", "wx", "yz"]
    assert len(digit_mapping) == 10

    # 生成数字到字母的映射
    letters = [digit_mapping[digit] for digit in num_digits]

    def dfs(letters, letter_index, path, result, visited):
        # 如果所有的字母都访问过了, 那就返回
        if letter_index >= len(letters):
            # 将当前路径上的字母加入到结果中
            substr = "".join(path)
            # 过滤字符串
            if filter_str not in substr:
                result.append(substr)
            return
        # 遍历当前索引位置的所有字母
        for char in letters[letter_index]:
            # 如果
            if char not in visited:
                path.append(char)
                visited.add(char)
                # 访问下一个字母组合
                dfs(letters, letter_index + 1, path, result, visited)
                # 将字母从临时路径中移除
                path.pop()
                # 将字母从访问过的记录中移除
                visited.remove(char)

    # 存放最后的结果
    result = []
    # 临时存放经过的路径
    path = []
    # 标记已访问过的字母
    visited = set()
    dfs(letters, 0, path, result, visited)

    # 打印结果
    print(",".join(result), ",", sep="")

if __name__ == "__main__":
    main()