2023年华为OD机考真题：字母组合

算法刷题1年前 (2023)更新江南白衣

全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。

真题库：https://www.yuque.com/codernav.com/od

题目：字母组合
知识点回溯
时间限制：1s 空间限制：256MB 限定语言：不限
题目描述：
每个数字对应多个字母，对应关系如下：
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,
解题思路：
回溯法求出所有可能的字母组合，并筛选出符合要求的（去除不能出现的字符）

代码实现一：

package com.codernav.demo.hwod.exam;

import java.util.Scanner;

/**
 * @title 字母组合
 * @Description 每个数字对应多个字母，对应关系如下：
 * 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；
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/28
 */
public class Main {
    public static String noContain;
    public static StringBuffer res = new StringBuffer();
    public static char[][] digits = {
            {'a', 'b', 'c'},
            {'d', 'e', 'f'},
            {'g', 'h', 'i'},
            {'j', 'k', 'l'},
            {'m', 'n', 'o'},
            {'p', 'q', 'r'},
            {'s', 't'},
            {'u', 'v'},
            {'w', 'x'},
            {'y', 'z'}
    };

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String numStr = sc.nextLine();
        noContain = sc.nextLine();      //不包含的字符串
        handle(0, numStr, "");
        System.out.println(res);
    }

    /**
     * 回溯法求出所有可能的字母组合，并筛选出符合要求的（去除不能出现的字符）
     *
     * @param index  字母索引
     * @param numStr 输入的数字字符串
     * @param temp   字母组合
     */
    public static void handle(int index, String numStr, String temp) {
        if (temp.length() == numStr.length()) {   //字符串的长度等于数字字符串的长度说明已经遍历完成
            if (isTrue(temp)) {      //字符串不包含noContain的进行拼接
                res.append(temp + ",");
            }
        } else {
            int digitsIndex = numStr.charAt(index) - '0';   //字母的索引
            char[] chars = digits[digitsIndex];
            for (int i = 0; i < chars.length; i++) {
                handle(index + 1, numStr, temp + chars[i]);
            }
        }
    }

    /**
     * 屏蔽字符中的所有字母是否同时出现
     *
     * @param str
     * @return
     */
    public static boolean isTrue(String str) {
        for (int i = 0; i < noContain.length(); i++) {
            String c = String.valueOf(noContain.charAt(i));
            if (!str.contains(c)) {   //只要有一个没有出现，就满足要求
                return true;
            }
        }
        return false;
    }
}

代码实现二：Java满分代码实现

package com.codernav.demo.hwod.exam;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * @title 字母组合
 * @Description 每个数字对应多个字母，对应关系如下：
 * 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；
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/28
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str1 = sc.nextLine();
        String str2 = sc.nextLine();
        List<String[]> list = initList();
        List<String[]> indexList = new ArrayList<>();
        int n = str1.length();
        for (int i = 0; i < n; i++) {
            int index = Integer.parseInt(str1.substring(i, i + 1));
            indexList.add(list.get(index));
        }
        List<String> arr = Arrays.asList(indexList.get(0));
        for (int i = 1; i < indexList.size(); i++) {
            arr = build(arr, indexList.get(i));
        }

        for (String str : arr) {
            if (check(str, str2)) {
                System.out.print(str + ",");
            }
        }
    }

    public static boolean check(String str, String checkStr) {
        for (int i = 0; i < checkStr.length(); i++) {
            if (!str.contains(checkStr.substring(i, i + 1))) {
                return true;
            }
        }
        return false;
    }

    public static List<String> build(List<String> str, String[] arr) {
        List<String> result = new ArrayList<>();
        for (int i = 0; i < str.size(); i++) {
            for (int j = 0; j < arr.length; j++) {
                result.add(str.get(i) + arr[j]);
            }
        }
        return result;
    }

    public static List<String[]> initList() {
        List<String[]> list = new ArrayList<>();
        list.add(new String[]{"a", "b", "c"});
        list.add(new String[]{"d", "e", "f"});
        list.add(new String[]{"g", "h", "i"});
        list.add(new String[]{"j", "k", "l"});
        list.add(new String[]{"m", "n", "o"});
        list.add(new String[]{"p", "q", "r"});
        list.add(new String[]{"s", "t"});
        list.add(new String[]{"u", "v"});
        list.add(new String[]{"w", "x"});
        list.add(new String[]{"y", "z"});
        return list;
    }
}