华为OD机试之过滤组合字符串（Java源码）

过滤组合字符串

题目描述
每个数字关联多个字母，关联关系如下：

输入描述

输出描述

用例

源码和解析
解析：

示例代码：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class T31 {
	static Map<Integer, List<Character>> map=new HashMap<Integer, List<Character>>(); //数字得到字符映射
	static String group[]=null; //记录dfs算法生成的数字组合
	static List<String> groupList=new ArrayList<>(); //最后生成的组合列表
	static StringBuilder sb=new StringBuilder();//用于循环产生一个字符串 主要针对于group数组
	public static void main(String[] args) {
		String cs[]={"abc","def","ghi","jkl","mno","pqr","st","uv","wx","yz"};
		String input1="789";
		String input2="ux";
		List<Integer> numList=new ArrayList<>();
		for(int i=0;i<input1.length();i++){
			numList.add(Integer.parseInt(input1.charAt(i)+""));
		}
		int count=0;
		for(int i=0;i<cs.length;i++){
			if(numList.contains(i)){
				List<Character> list=new ArrayList<Character>();
				for(int j=0;j<cs[i].length();j++){
					list.add(cs[i].charAt(j));
				}
				map.put(count++, list); //map中的索引要注意替换 方便dfs算法正常生效
			}
		}
//		System.out.println(map);
		group=new String[map.size()];
		dfs(0);
//		System.out.println(groupList);
		//过滤掉包含字符的
		for(String s:groupList){
			if(s.indexOf(input2)==-1){
				System.out.print(s+",");
			}
		}
	}
	public static void dfs(int p){
		if(p==map.size()){
			for(int i=0;i<group.length;i++){
				sb.append(group[i]);
			}
			groupList.add(sb.toString());
			sb.setLength(0);
			return;
		}
		for(int i=0;i<map.get(p).size();i++){
			group[p]=map.get(p).get(i)+"";
			dfs(p+1);
		}
	}
}

代码运行截图：