题目描述

给定一个数字字符串和一个屏蔽字符串，根据数字与字母的对应关系，生成所有可能的字符组合。要求在生成的字符串中，屏蔽字符串中的所有字母不能同时出现。如果屏蔽字符串是abc，则生成的字符串中不能同时包含a、b、c，但可以包含其中的任意一部分。

解题思路

1. 构建映射关系： 根据给定的数字与字母对应关系，建立一个映射表，方便查找。

2. 生成所有组合： 使用回溯算法递归地生成所有可能的字符组合。

3. 过滤组合： 对于每个生成的组合，检查其中是否包含屏蔽字符串中的所有字符，如果是，则过滤掉。

4. 输出结果： 将符合条件的组合按要求格式输出。

cpp

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>

using namespace std;

unordered_map<char, vector<char>> numToChar = {
    {'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'}}
};

void dfs(const string &digits, int index, string &current, vector<string> &result, const unordered_set<char> &blockSet) {
    if (index == digits.size()) {
        // 检查是否包含所有屏蔽字符
        bool hasAllBlockChars = true;
        for (char c : blockSet) {
            if (current.find(c) == string::npos) {
                hasAllBlockChars = false;
                break;
            }
        }
        if (!hasAllBlockChars) {
            result.push_back(current);
        }
        return;
    }
    char digit = digits[index];
    for (char c : numToChar[digit]) {
        current.push_back(c);
        dfs(digits, index + 1, current, result, blockSet);
        current.pop_back();
    }
}

int main() {
    string digits;
    string block;
    getline(cin, digits);
    getline(cin, block);

    unordered_set<char> blockSet(block.begin(), block.end());
    vector<string> result;
    string current;

    dfs(digits, 0, current, result, blockSet);

    for (const string &s : result) {
        cout << s << ",";
    }
    cout << endl;

    return 0;
}

python

import sys
from typing import List, Set

# 定义数字到字符的映射
num_to_char = {
    '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']
}

def dfs(digits: str, index: int, current: List[str], result: List[str], block_set: Set[str]):
    if index == len(digits):
        # 检查是否包含所有屏蔽字符
        has_all_block_chars = all(c in current for c in block_set)
        if not has_all_block_chars:
            result.append(''.join(current))
        return
    digit = digits[index]
    for c in num_to_char.get(digit, []):
        current.append(c)
        dfs(digits, index + 1, current, result, block_set)
        current.pop()

def main():
    # 读取输入
    digits = sys.stdin.readline().strip()
    block = sys.stdin.readline().strip()

    block_set = set(block)
    result = []
    current = []

    dfs(digits, 0, current, result, block_set)

    # 输出结果，用逗号分隔
    print(','.join(result) + ',')

if __name__ == "__main__":
    main()

java

import java.util.*;

public class Main {
    // 定义数字到字符的映射
    private static final Map<Character, List<Character>> numToChar = new HashMap<>();
    static {
        numToChar.put('0', Arrays.asList('a', 'b', 'c'));
        numToChar.put('1', Arrays.asList('d', 'e', 'f'));
        numToChar.put('2', Arrays.asList('g', 'h', 'i'));
        numToChar.put('3', Arrays.asList('j', 'k', 'l'));
        numToChar.put('4', Arrays.asList('m', 'n', 'o'));
        numToChar.put('5', Arrays.asList('p', 'q', 'r'));
        numToChar.put('6', Arrays.asList('s', 't'));
        numToChar.put('7', Arrays.asList('u', 'v'));
        numToChar.put('8', Arrays.asList('w', 'x'));
        numToChar.put('9', Arrays.asList('y', 'z'));
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String digits = scanner.nextLine().trim();
        String block = scanner.nextLine().trim();
        scanner.close();

        Set<Character> blockSet = new HashSet<>();
        for (char c : block.toCharArray()) {
            blockSet.add(c);
        }

        List<String> result = new ArrayList<>();
        StringBuilder current = new StringBuilder();

        dfs(digits, 0, current, result, blockSet);

        // 输出结果，用逗号分隔
        for (String s : result) {
            System.out.print(s + ",");
        }
        System.out.println();
    }

    private static void dfs(String digits, int index, StringBuilder current, List<String> result, Set<Character> blockSet) {
        if (index == digits.length()) {
            // 检查是否包含所有屏蔽字符
            boolean hasAllBlockChars = true;
            for (char c : blockSet) {
                if (current.indexOf(String.valueOf(c)) == -1) {
                    hasAllBlockChars = false;
                    break;
                }
            }
            if (!hasAllBlockChars) {
                result.add(current.toString());
            }
            return;
        }

        char digit = digits.charAt(index);
        List<Character> chars = numToChar.getOrDefault(digit, new ArrayList<>());
        for (char c : chars) {
            current.append(c);
            dfs(digits, index + 1, current, result, blockSet);
            current.deleteCharAt(current.length() - 1);
        }
    }
}

题目内容

每个数字关联多个字母，关联关系如下：

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