华为OD机试-过滤组合字符串-2022Q4 A卷-Py/Java/JS
数字0、1、2、3、4、5、6、7、8、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"
例如7关联"u","v"，8关联"x","w"，输入一个字符串例如“78”，
和一个屏蔽字符串“ux”,那么“78”可以组成多个字符串例如：“ux”，“uw”，“vx”，“vw”，过滤这些完全包含屏蔽字符串的每一个字符的字符串，然后输出剩下的字符串。
示例：
输入：
78
ux
输出：
uw vx vw
说明：ux完全包含屏蔽字符串ux，因此剔除
Java 代码
import java.util.Scanner;
import java.util.*;class Main {public static ArrayList<String> res_str_list;public static void main(String[] args) {// 处理输入Scanner in = new Scanner(System.in);String num_str = in.nextLine();String block_str = in.nextLine();//预设值HashMap<Character, String> num_char_map = new HashMap<Character, String>();num_char_map.put('0',"abc");num_char_map.put('1',"def");num_char_map.put('2',"ghi");num_char_map.put('3',"jkl");num_char_map.put('4',"mno");num_char_map.put('5',"pqr");num_char_map.put('6',"st");num_char_map.put('7',"uv");num_char_map.put('8',"wx");num_char_map.put('9',"yz");res_str_list = new ArrayList<String>();ArrayList<Character> char_list_temp = new ArrayList<Character>();dfs(num_str, char_list_temp, 0, num_char_map);int result_count = res_str_list.size();String output_str = "";for (String x : res_str_list) {// 过滤if (!check(x , block_str)) {output_str += x + " ";}}System.out.println(output_str.substring(0, output_str.length()-1));}//判断字符是否全部包含public static boolean check(String string1, String string2) {Set<Character> set1 = new HashSet<Character>();for (int i=0;i<string1.length();i++) {set1.add(string1.charAt(i));}Set<Character> set2 = new HashSet<Character>();for (int i=0;i<string2.length();i++) {set2.add(string2.charAt(i));}for (Character single_char : set2) { if (!set1.contains(single_char)){return false;}}return true;}// 递归求出所有可能的排列组合public static void dfs(String num_str, ArrayList<Character> list, int index, HashMap<Character, String> num_char_map) {if(index == num_str.length()) {String temp_str = "";for (int i=0;i<list.size();i++) {temp_str = temp_str + list.get(i);}res_str_list.add(temp_str);return;}for (char single_char : num_char_map.get(num_str.toCharArray()[index]).toCharArray()) {list.add(single_char);dfs(num_str, list, index+1, num_char_map);list.remove(list.size() - 1);}}}
Python代码
import functools
import copy
#保存排列组合字符串
res_str_list = []#预设值
num_char_map = {}
num_char_map['0'] = "abc"
num_char_map['1'] = "def"
num_char_map['2'] = "ghi"
num_char_map['3'] = "jkl"
num_char_map['4'] = "mno"
num_char_map['5'] = "pqr"
num_char_map['6'] = "st"
num_char_map['7'] = "uv"
num_char_map['8'] = "wx"
num_char_map['9'] = "yz"#递归求排列组合
def dfs(num_str, temp_list, index):if(index == len(num_str)):res_str_list.append("".join(temp_list))returntemp_list_back_up = copy.copy(temp_list)for single_char in num_char_map[num_str[index]]:temp_list.append(single_char)dfs(num_str, temp_list, index+1)temp_list.pop()#处理输入
num_str = input()
block_str = input()
dfs(num_str, [], 0)def check(string1, string2):set1 = set()for x in string1:set1.add(x)set2 = set()for x in string2:set2.add(x)for x in set2:if x not in set1:return Falsereturn True#过滤
for single_str in res_str_list:if check( single_str,block_str):res_str_list.remove(single_str)print (" ".join(res_str_list))JS代码
var char_map = ["abc", "def", "ghi", "jkl", "mno", "pqr", "st", "uv", "wx", "yz"]
var result = []function main(num_str, block_str) {var nums = num_str.split("").map((val) => char_map[val])block_str = [...block_str].sort().join("")dfs(nums, 0, [], block_str)console.log(result.join(" "))
}function check(string1, string2) {let set1 = new Set();for (let char of string1) {set1.add(char)}let set2 = new Set();for (let char of string2) {set2.add(char)}for (let char of set2) {if (!set1.has(char)){return false;}}return true;
}//排列组合用递归的方法即可
function dfs(nums, index, path, block_str) {if (index === nums.length) {if (!(check([...path].sort().join(""), block_str))) {result.push(path.join(""))}return}for (let j = 0; j < nums[index].length; j++) {path.push(nums[index][j])dfs(nums, index + 1, path, block_str)path.pop()}
}main("78", "ux")
