#P3236. 字母组合(200分)
-
1000ms
Tried: 83
Accepted: 30
Difficulty: 3
所属公司 :
华为od
字母组合(200分)
题目描述
给定一个数字字符串和一个屏蔽字符串,根据数字与字母的对应关系,生成所有可能的字符组合。要求在生成的字符串中,屏蔽字符串中的所有字母不能同时出现。如果屏蔽字符串是abc,则生成的字符串中不能同时包含a、b、c,但可以包含其中的任意一部分。
解题思路
-
构建映射关系: 根据给定的数字与字母对应关系,建立一个映射表,方便查找。
-
生成所有组合: 使用回溯算法递归地生成所有可能的字符组合。
-
过滤组合: 对于每个生成的组合,检查其中是否包含屏蔽字符串中的所有字符,如果是,则过滤掉。
-
输出结果: 将符合条件的组合按要求格式输出。
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 ¤t, 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,