E卷-字母组合(200分)

字母组合

问题描述

给定一个数字到字母的映射关系和一个屏蔽字符串，要求根据输入的数字字符串生成所有可能的字母组合，但需要排除包含屏蔽字符串中所有字母的组合。

数字到字母的映射关系如下：

• 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，但可以包含其中的一个或两个。

输入格式

输入包含两行：

1. 第一行是一个数字字符串，长度大于 0 且小于等于 5，其中的数字不允许重复。
2. 第二行是屏蔽字符串，长度小于数字字符串的长度，其中的字符不会重复。

输出格式

输出所有可能的字符串组合，每个字符串后面都要加上逗号，包括最后一个。

样例输入

78
ux

样例输出

uw,vw,vx,

样例解释

数字字符串 "78" 可以生成以下组合：uw、ux、vw、vx。 由于 "ux" 是屏蔽字符串，所以 "ux" 被排除，最终输出 uw、vw、vx。

数据范围

• 数字字符串长度：1 ≤ 长度 ≤ 5
• 屏蔽字符串长度 < 数字字符串长度

题解

这道题目的核心在于如何高效地生成所有可能的组合，并在生成过程中排除不符合要求的组合。

以下是解题思路：

1. 首先，创建一个数字到字母的映射字典，方便快速查找每个数字对应的字母。

2. 使用递归或回溯的方法生成所有可能的组合。在生成过程中，对于每个数字，我们尝试它对应的所有字母。

3. 在生成组合的同时，需要检查当前组合是否包含了屏蔽字符串中的所有字母。可以使用一个计数器来记录已匹配的屏蔽字符数量。

4. 如果在某个组合中，屏蔽字符的匹配数量等于屏蔽字符串的长度，则说明这个组合包含了所有屏蔽字符，应该被排除。

5. 当生成的组合长度等于数字字符串的长度时，如果该组合有效（不包含所有屏蔽字符），则将其添加到结果列表中。

6. 最后，按要求格式化输出结果。

这种方法的时间复杂度为 ，其中 是数字字符串的长度。这是因为在最坏情况下（每个数字对应 3 个字母），我们需要生成 个组合。

参考代码

以下是五种语言的参考代码实现：

• Python

# 定义数字到字母的映射
digit_to_letters = {
    '0': 'abc', '1': 'def', '2': 'ghi', '3': 'jkl', '4': 'mno',
    '5': 'pqr', '6': 'st', '7': 'uv', '8': 'wx', '9': 'yz'
}

def generate_combinations(digits, block, index, current, result, block_count):
    # 如果当前组合长度等于数字字符串长度，检查是否有效
    if len(current) == len(digits):
        if block_count < len(block):
            result.append(current)
        return
    
    # 获取当前数字对应的字母
    letters = digit_to_letters[digits[index]]
    for letter in letters:
        # 检查当前字母是否在屏蔽字符串中
        new_block_count = block_count + (letter in block)
        # 如果屏蔽字符数量未超过限制，继续递归
        if new_block_count < len(block):
            generate_combinations(digits, block, index + 1, current + letter, result, new_block_count)

# 主函数
def main():
    # 读取输入
    digits = input().strip()
    block = input().strip()
    
    # 生成组合
    result = []
    generate_combinations(digits, block, 0, "", result, 0)
    
    # 格式化输出
    print(','.join(result) + ',')

if __name__ == "__main__":
    main()

• C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 定义数字到字母的映射
const char *digitToLetters[] = {
    "abc", "def", "ghi", "jkl", "mno", "pqr", "st", "uv", "wx", "yz"
};

// 生成组合的递归函数
void generateCombinations(const char *digits, const char *block, int index, 
                          char *current, int currentLen, char **result, int *resultSize, int blockCount) {
    // 如果当前组合长度等于数字字符串长度，检查是否有效
    if (index == strlen(digits)) {
        if (blockCount < strlen(block)) {
            current[currentLen] = '\0';  // 结束当前字符串
            result[*resultSize] = (char *)malloc((currentLen + 1) * sizeof(char));
            strcpy(result[*resultSize], current);
            (*resultSize)++;
        }
        return;
    }
    
    // 获取当前数字对应的字母
    const char *letters = digitToLetters[digits[index] - '0'];
    for (int i = 0; letters[i] != '\0'; ++i) {
        char letter = letters[i];
        // 检查当前字母是否在屏蔽字符串中
        int newBlockCount = blockCount + (strchr(block, letter) != NULL);
        // 如果屏蔽字符数量未超过限制，继续递归
        if (newBlockCount < strlen(block)) {
            current[currentLen] = letter;  // 将当前字母加入到组合中
            generateCombinations(digits, block, index + 1, current, currentLen + 1, result, resultSize, newBlockCount);
        }
    }
}

int main() {
    char digits[100], block[100];
    
    // 读取输入
    scanf("%s %s", digits, block);
    
    // 准备存储结果的数组
    char *result[1000];
    int resultSize = 0;
    char current[100];
    
    // 生成组合
    generateCombination