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
- 屏蔽字符串长度 < 数字字符串长度
题解
这道题目的核心在于如何高效地生成所有可能的组合,并在生成过程中排除不符合要求的组合。
以下是解题思路:
-
首先,创建一个数字到字母的映射字典,方便快速查找每个数字对应的字母。
-
使用递归或回溯的方法生成所有可能的组合。在生成过程中,对于每个数字,我们尝试它对应的所有字母。
-
在生成组合的同时,需要检查当前组合是否包含了屏蔽字符串中的所有字母。可以使用一个计数器来记录已匹配的屏蔽字符数量。
-
如果在某个组合中,屏蔽字符的匹配数量等于屏蔽字符串的长度,则说明这个组合包含了所有屏蔽字符,应该被排除。
-
当生成的组合长度等于数字字符串的长度时,如果该组合有效(不包含所有屏蔽字符),则将其添加到结果列表中。
-
最后,按要求格式化输出结果。
这种方法的时间复杂度为 ,其中 是数字字符串的长度。这是因为在最坏情况下(每个数字对应 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];
// 生成组合
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();
}
}
- Cpp
#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#本专栏收集并整理了一些刷题笔记