每个数字对应多个字母，对应关系如下：
0：a,b,c1：d,e,f2：g,h,i3：j,k,l4：m,n,o5：p,q,r6：s,t7：u,v8：w,x9：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；
第二行输入是屏蔽字符，屏蔽字符的长度一定小于数字字符串的长度，屏蔽字符串中字符不会重复，
输出可能的字符串组合
注：字符串之间使用逗号隔开，最后一个字符串后携带逗号
78
ux
uw,vw,vx,
78
x
uw,vw,
本题要求将一串数字字符串根据预定义的数字与字母映射关系转换为字母组合，但需要遵循一个约束条件，即结果字符串中不能包含屏蔽字符串的所有字符。为了实现这个功能，我们可以使用递归来遍历所有可能的字母组合，然后根据约束条件对结果进行筛选。
首先，我们需要一个数组或列表来存储每个数字对应的字母集合。接下来，我们可以编写一个递归函数，用于遍历所有可能的字母组合。这个递归函数接受四个参数：输入的数字字符串、屏蔽字符串、当前生成的组合字符串以及一个表示当前递归层级的整数。
在递归函数中，我们首先检查当前层级是否已经达到了数字字符串的长度。如果是，则说明我们已经生成了一个完整的字母组合。在这种情况下，我们需要检查这个组合是否满足约束条件。我们可以通过计算屏蔽字符串中每个字符在组合字符串中出现的次数来实现这一点。如果屏蔽字符串中的所有字符都未同时出现在组合字符串中，则说明这个组合是有效的，我们可以将其输出。
如果当前层级尚未达到数字字符串的长度，则我们需要继续生成更长的组合。为了实现这一点，我们首先根据当前层级的数字字符获取对应的字母集合。然后，我们遍历这个字母集合，将每个字母依次添加到组合字符串的当前位置，然后递归地调用函数本身，将层级加一。当递归返回时，我们可以继续尝试下一个字母。
在主函数中，我们需要读取输入的数字字符串和屏蔽字符串，然后创建一个缓冲字符串来存储当前生成的组合。接着，我们调用递归函数，从第一层级开始生成组合。当所有可能的组合都被输出时，程序结束。
时间复杂度：对于每个数字，我们需要遍历其对应的字母集合。最坏情况下，输入的数字字符串长度为5，每个数字对应的字母数量为3。因此，总共需要遍历 3^5 = 243 种组合。在每个组合上，我们还需要检查屏蔽字符串中的字符是否同时出现，这需要 O(L) 时间，其中 L 是屏蔽字符串的长度。因此，总的时间复杂度为 O(243L)。
空间复杂度：我们需要一个缓冲字符串来存储当前生成的组合，其长度等于数字字符串的长度。此外，在递归过程中，我们需要使用额外的栈空间来存储函数调用的上下文。最大递归深度等于数字字符串的长度。因此，总的空间复杂度为 O(N)，其中 N 是数字字符串的长度。
这个问题可以通过递归的方法来解决，遍历所有可能的字母组合，然后根据约束条件进行筛选。时间复杂度为 O(243L)，空间复杂度为 O(N)。虽然在最坏情况下，时间复杂度相对较高，但由于输入规模较小（数字字符串长度最大为5），因此在实际应用中，这种方法的性能是可以接受的。同时，这种方法具有很好的可扩展性，可以很容易地适应更复杂的映射关系和约束条件。
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
const char *digit_to_letters[] = {
"abc", "def", "ghi", "jkl", "mno", "pqr", "st", "uv", "wx", "yz"
};
void print_combinations(const char *digits, const char *block, char *buffer, int level) {
if (digits[level] == '\0') {
bool valid = true;
for (int i = 0; block[i] != '\0'; ++i) {
int count = 0;
for (int j = 0; buffer[j] != '\0'; ++j) {
if (buffer[j] == block[i]) {
count++;
}
}
if (count == strlen(block)) {
valid = false;
break;
}
}
if (valid) {
printf("%s,", buffer);
}
return;
}
int digit = digits[level] - '0';
const char *letters = digit_to_letters[digit];
for (int i = 0; letters[i] != '\0'; ++i) {
buffer[level] = letters[i];
buffer[level + 1] = '\0';
print_combinations(digits, block, buffer, level + 1);
}
}
int main() {
char digits[6];
char block[6];
char buffer[6];
scanf("%s", digits);
scanf("%s", block);
print_combinations(digits, block, buffer, 0);
return 0;
}
#include <iostream>
#include <string>
#include <vector>
const std::vector<std::string> digit_to_letters{
"abc", "def", "ghi", "jkl", "mno", "pqr", "st", "uv", "wx", "yz"
};
void print_combinations(const std::string &digits, const std::string &block, std::string &buffer, int level) {
if (level == digits.size()) {
bool valid = true;
for (char ch : block) {
int count = 0;
for (char buf_ch : buffer) {
if (buf_ch == ch) {
count++;
}
}
if (count == block.size()) {
valid = false;
break;
}
}
if (valid) {
std::cout << buffer << ",";
}
return;
}
int digit = digits[level] - '0';
const std::string &letters = digit_to_letters[digit];
for (char letter : letters) {
buffer[level] = letter;
print_combinations(digits, block, buffer, level + 1);
}
}
int main() {
std::string digits;
std::string block;
std::string buffer;
std::cin >> digits >> block;
buffer.resize(digits.size());
print_combinations(digits, block, buffer, 0);
return 0;
}
import java.util.*;
/**
* Created with IntelliJ IDEA.
* <br>Author: Amos
* <br>E-mail: amos@amoscloud.com
* <br>Date: 2023/2/28
* <br>Time: 5:33
* <br>Description:
*/
public class Main0223 {
private static final String[] KB = {"abc", "def", "ghi", "jkl", "mno", "pqr", "st", "uv", "wx", "yz"};
public static void main(String[] args) {
try (Scanner scanner = new Scanner(System.in)) {
Integer[] arr =
Arrays.stream(scanner.next().split("")).map(Integer::parseInt).toArray(Integer[]::new);
String filter = scanner.next();
System.out.println(solution(arr, filter));
}
}
public static String solution(Integer[] arr, String filter) {
String[] newArr = Arrays.stream(arr).map(val -> KB[val]).toArray(String[]::new);
char[] cArr = filter.toCharArray();
Arrays.sort(cArr);
filter = new String(cArr);
ArrayList<String> res = new ArrayList<>();
dfs(newArr, 0, new LinkedList<>(), res, filter);
StringJoiner sj = new StringJoiner(" ", "", "");
for (String str : res) {
sj.add(str);
}
return sj.toString();
}
public static void dfs(
String[] arr, int index, LinkedList<Character> path, ArrayList<String> res, String filter) {
if (index == arr.length) {
if (!include(path, filter)) {
StringBuilder sb = new StringBuilder();
for (Character c : path) {
sb.append(c);
}
res.add(sb.toString());
}
return;
}
for (int i = 0; i < arr[index].length(); i++) {
path.addLast(arr[index].charAt(i));
dfs(arr, index + 1, path, res, filter);
path.removeLast();
}
}
public static boolean include(LinkedList<Character> path, String filter) {
StringBuilder sb = new StringBuilder();
path.stream().sorted().forEach(sb::append);
String src = sb.toString();
if (filter.length() > src.length()) return false;
int i = 0;
int j = 0;
while (i < src.length() && j < filter.length()) {
if (src.charAt(i) == filter.charAt(j)) j++;
i++;
}
return j == filter.length();
}
}
digit_to_letters = [
"abc", "def", "ghi", "jkl", "mno", "pqr", "st", "uv", "wx", "yz"
]
def print_combinations(digits, block, buffer, level):
if level == len(digits):
if not all(buffer.count(ch) == len(block) for ch in block):
print("".join(buffer), end=",")
return
digit = int(digits[level])
letters = digit_to_letters[digit]
for letter in letters:
buffer[level] = letter
print_combinations(digits, block, buffer, level + 1)
if __name__ == "__main__":
digits = input().strip()
block = input().strip()
buffer = [None] * len(digits)
print_combinations(digits, block, buffer, 0)
const digitToLetters = [
"abc", "def", "ghi", "jkl", "mno", "pqr", "st", "uv", "wx", "yz"
];
function printCombinations(digits, block, buffer, level) {
if (level === digits.length) {
const valid = !block.every(ch => buffer.filter(bufCh => bufCh === ch).length === block.length);
if (valid) {
console.log(buffer.join('') + ",");
}
return;
}
const digit = parseInt(digits[level], 10);
const letters = digitToLetters[digit];
for (const letter of letters) {
buffer[level] = letter;
printCombinations(digits, block, buffer, level + 1);
}
}
const [digits, block] = require('fs').readFileSync(0, 'utf-8').trim().split('\n');
const buffer = Array(digits.length);
printCombinations(digits, block, buffer, 0);
package main
import (
"bufio"
"fmt"
"os"
"strconv"
)
var digitToLetters = []string{
"abc", "def", "ghi", "jkl", "mno", "pqr", "st", "uv", "wx", "yz",
}
func printCombinations(digits, block string, buffer []rune, level int) {
if level == len(digits) {
valid := true
for _, ch := range block {
count := 0
for _, bufCh := range buffer {
if bufCh == ch {
count++
}
}
if count == len(block) {
valid = false
break
}
}
if valid {
fmt.Printf("%s,", string(buffer))
}
return
}
digit, _ := strconv.Atoi(string(digits[level]))
letters := digitToLetters[digit]
for _, letter := range letters {
buffer[level] = letter
printCombinations(digits, block, buffer, level+1)
}
}
func main() {
scanner := bufio.NewScanner(os.Stdin)
scanner.Scan()
digits := scanner.Text()
scanner.Scan()
block := scanner.Text()
buffer := make([]rune, len(digits))
printCombinations(digits, block, buffer, 0)
}