2025 A卷 100分 题型

本专栏内全部题目均提供Java、python、JavaScript、C、C++、GO六种语言的最佳实现方式；

并且每种语言均涵盖详细的问题分析、解题思路、代码实现、代码详解、3个测试用例以及综合分析；

本文收录于专栏：《2025华为OD真题目录+全流程解析+备考攻略+经验分享》

华为OD机试真题《字母组合过滤组合字符串》：

---

文章快捷目录

题目描述及说明

Java

python

JavaScript

C

GO

---

题目名称：字母组合过滤组合字符串

---

知识点：字符串、回溯算法、逻辑处理
时间限制：1秒
空间限制：256MB
限定语言：不限

---

题目描述

数字0-9分别关联a~z的26个英文字母，具体对应关系如下：

• 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”

输入要求：

1. 第一行为一串不重复的数字字符串，长度范围1-5。
2. 第二行为屏蔽字符串，其长度小于数字字符串长度，且字符不重复。

输出要求：

• 根据数字顺序生成所有可能的字母组合字符串。
• 若组合字符串完全包含屏蔽字符串的所有字符（即屏蔽字符串的每个字符均出现在组合中），则剔除该组合。
• 输出剩余的组合字符串，用逗号分隔，末尾带逗号。

示例1：
输入：

78  
ux  

输出：

uw,vw,vx,  

说明：数字"7"对应"u",“v”，“8"对应"w”,“x”，生成组合为[“uw”,“ux”,“vw”,“vx”]。其中"ux"完全包含屏蔽字符串"ux"，故剔除。

示例2：
输入：

23  
jl  

输出：

jk,jl,kl,  

说明：数字"2"对应"g",“h”,“i”，“3"对应"j”,“k”,“l”，生成组合中"jl"包含屏蔽字符串"jl"，需剔除。

---

Java

问题分析

题目要求根据数字到字母的映射生成所有可能的组合字符串，并过滤掉包含屏蔽字符串所有字符的组合。需要处理以下问题：

1. 数字到字母的映射：每个数字对应一组字母。
2. 生成所有组合：通过回溯算法生成所有可能的字母组合。
3. 过滤条件：剔除完全包含屏蔽字符串所有字符的组合。

---

解题思路

1. 映射表构建：预定义数字到字母的映射关系。
2. 回溯生成组合：递归生成所有可能的字母组合。
3. 过滤与输出：检查每个组合是否包含屏蔽字符串的所有字符，剔除符合条件的组合后排序输出。

---

代码实现

import java.util.*;public class Main {private static final String[] MAPPING = {"abc", "def", "ghi", "jkl", "mno", "pqr", "st", "uv", "wx", "yz"};public static void main(String[] args) {Scanner sc = new Scanner(System.in);String digits = sc.nextLine().trim();String block = sc.nextLine().trim();List<String> combinations = new ArrayList<>();if (!digits.isEmpty()) {backtrack(combinations, digits, new StringBuilder(), 0);}Set<Character> blockSet = new HashSet<>();for (char c : block.toCharArray()) {blockSet.add(c);}List<String> filtered = new ArrayList<>();for (String s : combinations) {if (!containsAll(s, blockSet)) {filtered.add(s);}}Collections.sort(filtered);StringBuilder sb = new StringBuilder();for (String s : filtered) {sb.append(s).append(',');}System.out.println(sb.toString());}private static void backtrack(List<String> result, String digits, StringBuilder current, int index) {if (index == digits.length()) {result.add(current.toString());return;}int digit = digits.charAt(index) - '0';String letters = MAPPING[digit];for (char c : letters.toCharArray()) {current.append(c);backtrack(result, digits, current, index + 1);current.deleteCharAt(current.length() - 1);}}private static boolean containsAll(String s, Set<Character> blockSet) {for (char c : blockSet) {if (s.indexOf(c) == -1) {return false;}}return true;}
}

---

代码详解

1. 映射表定义：

   private static final String[] MAPPING = { ... };
   

   • 使用数组 MAPPING 存储数字到字母的映射，索引对应数字，值为字母字符串。

2. 输入处理：

   String digits = sc.nextLine().trim();
   String block = sc.nextLine().trim();
   

   • 读取输入的数字字符串和屏蔽字符串。

3. 回溯生成组合：

   backtrack(combinations, digits, new StringBuilder(), 0);
   

   • 调用 backtrack 方法生成所有可能的组合。
   • 递归终止条件：当 index 等于数字字符串长度时，将当前组合加入结果列表。
   • 遍历字母：对当前数字对应的每个字母，递归生成后续组合。

4. 过滤条件检查：

   private static boolean containsAll(String s, Set<Character> blockSet) {for (char c : blockSet) {if (s.indexOf(c) == -1) {return false;}}return true;
   }
   

   • 检查组合字符串 s 是否包含屏蔽字符串的所有字符。

5. 结果处理与输出：

   Collections.sort(filtered);
   StringBuilder sb = new StringBuilder();
   for (String s : filtered) {sb.append(s).append(',');
   }
   System.out.println(sb.toString());
   

   • 对过滤后的结果排序，并按逗号分隔输出。

---

示例测试

1. 示例1输入：

   78  
   ux  
   

   输出：

   uw,vw,vx,  
   

   说明：组合 “ux” 包含所有屏蔽字符，被过滤。

2. 示例2输入：

   23  
   jl  
   

   输出：

   jk,jl,kl,  
   

   说明：组合 “jl” 包含所有屏蔽字符，被过滤。

3. 测试用例：
   输入：

   5  
   pq  
   

   输出：

   p,q,r,  
   

   说明：屏蔽字符串 “pq” 未被任何组合包含，所有组合保留。

---

综合分析

1. 时间复杂度：

   • 生成组合：O(3^N)，每个数字最多对应3个字母，N为数字字符串长度。
   • 过滤与排序：O(M log M)，M为生成组合的数量。

2. 空间复杂度：

   • O(3^N)，存储所有组合字符串。

3. 正确性：

   • 通过回溯遍历所有可能的组合，确保生成完整的解空间。
   • 严格检查每个组合是否包含屏蔽字符串的所有字符。

4. 适用性：

   • 适用于数字字符串长度1~5的情况，符合题目限制。

5. 优化点：

   • 剪枝策略：在生成组合的过程中可提前判断是否可能包含屏蔽字符，减少无效递归。
   • 空间优化：直接生成过滤后的结果，减少存储开销。

---

python

问题分析

题目要求根据数字到字母的映射生成所有可能的组合字符串，并过滤掉完全包含屏蔽字符串所有字符的组合。需要解决以下问题：

1. 数字到字母的映射：每个数字对应一组字母。
2. 生成所有组合：通过回溯算法生成所有可能的字母组合。
3. 过滤条件：剔除包含屏蔽字符串所有字符的组合。

---

解题思路

1. 映射表构建