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

输入格式

输入包含两行：

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

输出格式

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

样例输入

78
ux

样例输出

uw,vw,vx,

样例解释

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

数据范围

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

题解

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

以下是解题思路：

首先，创建一个数字到字母的映射字典，方便快速查找每个数字对应的字母。
使用递归或回溯的方法生成所有可能的组合。在生成过程中，对于每个数字，我们尝试它对应的所有字母。
在生成组合的同时，需要检查当前组合是否包含了屏蔽字符串中的所有字母。可以使用一个计数器来记录已匹配的屏蔽字符数量。
如果在某个组合中，屏蔽字符的匹配数量等于屏蔽字符串的长度，则说明这个组合包含了所有屏蔽字符，应该被排除。
当生成的组合长度等于数字字符串的长度时，如果该组合有效（不包含所有屏蔽字符），则将其添加到结果列表中。
最后，按要求格式化输出结果。

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

参考代码

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

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()

#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];
    
    // 生成组合
    generateCombinations(digits, block, 0, current, 0, result, &resultSize, 0);
    
    // 格式化输出
    for (int i = 0; i < resultSize; ++i) {
        printf("%s,", result[i]);
        free(result[i]); // 释放动态分配的内存
    }
    printf("\n");
    
    return 0;
}

Javascript

// 导入 readline 模块，用于处理命令行输入
const readline = require('readline');

// 定义数字到字母的映射
// 每个数字对应一组字母
const digitToLetters = {
    '0': 'abc', '1': 'def', '2': 'ghi', '3': 'jkl', '4': 'mno',
    '5': 'pqr', '6': 'st', '7': 'uv', '8': 'wx', '9': 'yz'
};

/**
 * 生成组合的递归函数
 * @param {string} digits - 输入的数字字符串
 * @param {string} block - 屏蔽字符串
 * @param {number} index - 当前处理的数字索引
 * @param {string} current - 当前生成的组合
 * @param {string[]} result - 存储结果的数组
 * @param {number} blockCount - 当前组合中屏蔽字符的数量
 */
function generateCombinations(digits, block, index, current, result, blockCount) {
    // 基本情况：如果已经处理完所有数字
    if (index === digits.length) {
        // 如果屏蔽字符数量小于屏蔽字符串长度，则添加到结果中
        if (blockCount < block.length) {
            result.push(current);
        }
        return;
    }
    
    // 获取当前数字对应的字母
    const letters = digitToLetters[digits[index]];
    // 遍历当前数字对应的每个字母
    for (let i = 0; i < letters.length; i++) {
        const letter = letters[i];
        // 计算新的屏蔽字符数量
        const newBlockCount = blockCount + (block.indexOf(letter) !== -1 ? 1 : 0);
        // 如果新的屏蔽字符数量小于屏蔽字符串长度，继续递归
        if (newBlockCount < block.length) {
            generateCombinations(digits, block, index + 1, current + letter, result, newBlockCount);
        }
    }
}

// 创建 readline 接口，用于读取用户输入
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

/**
 * 主函数，处理输入并调用生成组合的函数
 */
function main() {
    // 读取第一行输入（数字字符串）
    rl.question('', (digits) => {
        // 读取第二行输入（屏蔽字符串）
        rl.question('', (block) => {
            // 初始化结果数组
            const result = [];
            // 调用生成组合的函数
            generateCombinations(digits.trim(), block.trim(), 0, "", result, 0);
            // 格式化并输出结果
            console.log(result.join(',') + ',');
            // 关闭 readline 接口
            rl.close();
        });
    });
}

// 调用主函数
main();

Java

import java.util.*;

public class Main {
    // 定义数字到字母的映射
    private static final String[] DIGIT_TO_LETTERS = {
        "abc", "def", "ghi", "jkl", "mno", "pqr", "st", "uv", "wx", "yz"
    };

    public static void generateCombinations(String digits, String block, int index, 
                                            StringBuilder current, List<String> result, int blockCount) {
        // 如果当前组合长度等于数字字符串长度，检查是否有效
        if (index == digits.length()) {
            if (blockCount < block.length()) {
                result.add(current.toString());
            }
            return;
        }
        
        // 获取当前数字对应的字母
        String letters = DIGIT_TO_LETTERS[digits.charAt(index) - '0'];
        for (char letter : letters.toCharArray()) {
            // 检查当前字母是否在屏蔽字符串中
            int newBlockCount = blockCount + (block.indexOf(letter) != -1 ? 1 : 0);
            // 如果屏蔽字符数量未超过限制，继续递归
            if (newBlockCount < block.length()) {
                current.append(letter);
                generateCombinations(digits, block, index + 1, current, result, newBlockCount);
                current.setLength(current.length() - 1);
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        String digits = scanner.nextLine().trim();
        String block = scanner.nextLine().trim();
        
        // 生成组合
        List<String> result = new ArrayList<>();
        generateCombinations(digits, block, 0, new StringBuilder(), result, 0);
        
        // 格式化输出
        System.out.println(String.join(",", result) + ",");
        
        scanner.close();
    }
}

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// 定义数字到字母的映射
const vector<string> digitToLetters = {
    "abc", "def", "ghi", "jkl", "mno", "pqr", "st", "uv", "wx", "yz"
};

void generateCombinations(const string& digits, const string& block, int index, 
                          string& current, vector<string>& result, int blockCount) {
    // 如果当前组合长度等于数字字符串长度，检查是否有效
    if (index == digits.length()) {
        if (blockCount < block.length()) {
            result.push_back(current);
        }
        return;
    }
    
    // 获取当前数字对应的字母
    const string& letters = digitToLetters[digits[index] - '0'];
    for (char letter : letters) {
        // 检查当前字母是否在屏蔽字符串中
        int newBlockCount = blockCount + (block.find(letter) != string::npos);
        // 如果屏蔽字符数量未超过限制，继续递归
        if (newBlockCount < block.length()) {
            current.push_back(letter);
            generateCombinations(digits, block, index + 1, current, result, newBlockCount);
            current.pop_back();
        }
    }
}

int main() {
    string digits, block;
    
    // 读取输入
    cin >> digits >> block;
    
    // 生成组合
    vector<string> result;
    string current;
    generateCombinations(digits, block, 0, current, result, 0);
    
    // 格式化输出
    for (const auto& s : result) {
        cout << s << ",";
    }
    cout << endl;
    
    return 0;
}

#E##OD#

OD刷题笔记文章被收录于专栏

本专栏收集并整理了一些刷题笔记