当前位置：首页 > news >正文

华为OD机试 - 过滤组合字符串 - 深度优先搜索dfs算法（Java 2023 B卷 100分）

news 2025/8/10 1:21:10

在这里插入图片描述

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷）》。

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

每个数字关联多个字母，关联关系如下：

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。

二、输入描述

第一行输入为一串数字字符串，数字字符串中的数字不允许重复，数字字符串的长度大于0，小于等于5；
第二行输入是屏蔽字符串，屏蔽字符串的长度一定小于数字字符串的长度，屏蔽字符串中字符不会重复；

三、输出描述

输出可能的字符串组合

注：字符串之间使用逗号隔开，最后一个字符串后携带逗号

四、解题思路

定义数组arr，存储每个数字关联多个字母；
第一行输入为一串数字字符串；
第二行输入是屏蔽字符串；
定义集合list，加载第一行字母关联的数字；
并将集合list加载到map中；
使用深度优先搜索dfs算法，遍历map；
输出所有可能的输出可能的字符串组合。

五、Java算法源码

package com.guor.od;import java.util.*;public class OdTest {static Map<Integer, List<Character>> map = new HashMap<Integer, List<Character>>();static String[] numArr = null;static List<String> okList = new ArrayList<>();public static void main(String[] args) {// 每个数字关联多个字母，关联关系如下String[] arr = {"abc", "def", "ghi", "jkl", "mno", "pqr", "st", "uv", "wx", "yz"};Scanner sc = new Scanner(System.in);String input1 = sc.nextLine();String input2 = sc.nextLine();List<Integer> numberList = new ArrayList<>();for (int i = 0; i < input1.length(); i++) {numberList.add(Integer.parseInt(input1.charAt(i) + ""));}int count = 0;for (int i = 0; i < arr.length; i++) {if (numberList.contains(i)) {// 第一行字母关联的数字List<Character> list = new ArrayList<Character>();for (int j = 0; j < arr[i].length(); j++) {list.add(arr[i].charAt(j));}map.put(count++, list);}}numArr = new String[map.size()];dfs(0);for (String s : okList) {if (s.indexOf(input2) == -1) {System.out.print(s + ",");}}}static StringBuilder builder = new StringBuilder();public static void dfs(int num) {if (num == map.size()) {for (int i = 0; i < numArr.length; i++) {builder.append(numArr[i]);}okList.add(builder.toString());builder.setLength(0);return;}for (int i = 0; i < map.get(num).size(); i++) {numArr[num] = map.get(num).get(i) + "";dfs(num + 1);}}
}