【华为OD-E卷-27 字母组合 100分（python、java、c++、js、c）】

【华为OD-E卷-字母组合 100分（python、java、c++、js、c）】

题目

每个数字关联多个字母，关联关系如下：
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；

第二行输入是屏蔽字符串，屏蔽字符串的长度一定小于数字字符串的长度，屏蔽字符串中字符不会重复

输出描述

  • 输出可能的字符串组合

用例

用例一：
输入：
78
ux
  • 1
  • 2
输出：
uw,vw,vx,
  • 1
用例二：
输入：
78
x
  • 1
  • 2
输出：
uw,vw,
  • 1

python解法

  • 解题思路：
  • 字母映射关系： 每个数字（从0到9）映射到一定的字母集合。例如，数字2对应字母"abc"，数字3对应字母"def"。通过一个 char_map 列表来记录这些映射关系。char_map[i] 表示数字 i 对应的字母集合。

队列（Queue）用于生成组合： 我们使用一个队列来逐步生成所有可能的字母组合。每次从队列中取出一个当前的组合（初始为空字符串""），然后将每个字母组合进来，形成新的组合，继续加入队列。

过滤条件： 在生成每一个新的字母组合时，判断这个组合是否包含屏蔽字符串中的所有字符。如果不包含，则将这个组合加入队列。过滤条件由 contains_all 函数检查，确保新生成的组合满足不含有屏蔽字符串的所有字符。

最终返回： 经过所有处理后，所有符合条件的字母组合会在队列中。最终将这些组合合并成一个字符串，返回。

from collections import deque

# 获取符合条件的所有字母组合
def get_combinations(nums, filter_str):
    # 数字到字母的映射，数字0对应"abc"，数字1对应"def"等
    char_map = ["abc", "def", "ghi", "jkl", "mno", "pqr", "st", "uv", "wx", "yz"]

    # 使用队列存储生成的字母组合，初始时队列中只有空字符串
    queue = deque([""])

    # 对输入的每个数字进行处理
    for num in nums:
        # 获取当前数字对应的字母集合
        letters = char_map[int(num)]
        size = len(queue)

        # 对队列中当前的每个组合进行扩展
        for _ in range(size):
            # 取出队列中的一个组合
            path = queue.popleft()

            # 对当前组合，尝试添加所有可能的字母
            for letter in letters:
                # 生成新的组合
                new_path = path + letter

                # 如果新组合不包含屏蔽字符串中的所有字符，则加入队列
                if not contains_all(new_path, filter_str):
                    queue.append(new_path)

    # 返回符合条件的所有组合，多个组合用逗号分隔
    return ",".join(queue) + ","

# 检查组合是否包含屏蔽字符串中的所有字符
def contains_all(s, filter_str):
    # 遍历屏蔽字符串中的每个字符，检查它是否出现在当前组合中
    for c in filter_str:
        if c not in s:
            return False
    return True

# 输入处理
nums = input().strip()  # 输入数字串
filter_str = input().strip()  # 输入屏蔽字符串
print(get_combinations(nums, filter_str))  # 输出符合条件的字母组合
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46

java解法

  • 解题思路
  • 字母映射关系： 每个数字（0到9）对应一定的字母集合。可以使用一个数组 map 来表示这种映射关系。map[i] 表示数字 i 对应的字母集合。例如，map[2] 对应字母 “abc”。

生成所有字母组合： 由于输入的数字串 nums 可能对应多个字母，我们需要生成所有可能的字母组合。可以通过类似多重循环的方式生成这些组合，每个数字选择一个字母进行拼接。为了避免直接使用多层循环，我们使用一个数组 indices 来表示每个数字在其对应字母集合中的当前位置，然后利用该数组进行组合生成。

组合生成：

从左到右遍历每个数字，选择其对应字母集合中的一个字母。
使用一个 StringBuilder 来拼接当前组合，并将其加入结果列表 result，如果该组合不包含屏蔽字符串中的所有字符。
递增逻辑：

当我们生成一个字母组合后，需要递增组合的 “位置”。如果某一位的字母已经到达其字母集合的最后一个字母，则回退到该集合的第一个字母，并递增上一位。
如果所有的字母集合都回退到第一个字母，说明所有组合已经生成完毕。
返回结果：

最终，将所有符合条件的字母组合连接成一个以逗号分隔的字符串，返回。

import java.util.*;

public class Main {
    // 数字与字母的映射关系
    static String nums;
    static String filter;
    static String[] map = {"abc", "def", "ghi", "jkl", "mno", "pqr", "st", "uv", "wx", "yz"};
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 读取数字串和过滤字符串
        nums = sc.nextLine();
        filter = sc.nextLine();
        // 输出符合条件的字母组合
        System.out.println(getResult());
    }
    
    // 获取所有符合条件的字母组合
    public static String getResult() {
        int n = nums.length();  // 获取数字串长度
        int[] indices = new int[n];  // 数组用于跟踪每个数字对应字母集合中的当前位置
        List<String> result = new ArrayList<>();  // 存储符合条件的字母组合
        
        // 使用while循环生成所有可能的字母组合
        while (true) {
            StringBuilder sb = new StringBuilder();
            // 根据当前的 indices 数组生成字母组合
            for (int i = 0; i < n; i++) {
                sb.append(map[nums.charAt(i) - '0'].charAt(indices[i]));  // 通过 map 获取字母
            }
            // 如果字母组合不包含屏蔽字符串中的所有字符，则添加到结果列表
            if (!containsAll(sb.toString(), filter)) {
                result.add(sb.toString());
            }
            
            // 寻找下一个字母组合
            int pos = n - 1;  // 从最后一位开始查找
            while (pos >= 0) {
                // 如果当前位的字母集合还有更多的字母，递增该位的索引
                if (indices[pos] < map[nums.charAt(pos) - '0'].length() - 1) {
                    indices[pos]++;
                    break;
                } else {
                    // 如果该位已到达字母集合的最后一个字母，回退并继续递增上一位
                    indices[pos] = 0;
                    pos--;
                }
            }
            // 如果所有位都回退到最初的状态，说明已生成所有组合，跳出循环
            if (pos < 0) break;
        }
        
        // 将所有符合条件的组合以逗号分隔并返回
        return String.join(",", result) + ",";
    }
    
    // 检查字符串是否包含过滤字符串中的所有字符
    public static boolean containsAll(String s, String filter) {
        // 遍历过滤字符串中的每个字符，检查是否在当前组合中
        for (char c : filter.toCharArray()) {
            if (!s.contains(String.valueOf(c))) {
                return false;
            }
        }
        return true;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68

C++解法

  • 解题思路
更新中
  • 1

C解法

  • 解题思路

更新中
  • 1

JS解法

  • 解题思路

更新中
  • 1

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏

注：本文转载自blog.csdn.net的CodeClimb的文章"https://blog.csdn.net/CodeClimb/article/details/144514574"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！