问题
给定一个包含[0，9]中数字的整数数组，任务是打印所有可能的字母
数字可以表示的组合，数字到字母的映射（就像在电话按钮上）正在被跟踪，注意0和1不映射到任何字母。所有映射如下图所示：
写一个程序把0到9的数字转换成字母，且程序需要支持将0到99的数字转换成字母。
例如：
Input:arr[] ={3,4}
Output: DG DH DI EG EH EI FG FH FI
Input: arr[] = {2}
Output: A B C
解题思路
初始化数据
使用HashMap来存储数字和字母的映射关系，其中数字作为key，字母作为value，因为一个数字对应了多个字母，且每个数字对应的字母个数又不尽相同，所以这里的value使用List集合来进行存放。代码如下：
public static void initDigitsMap(){
digitsMap=new HashMap<>();
digitsMap.put("0",Arrays.asList(""));
digitsMap.put("1",Arrays.asList(""));
digitsMap.put("2",Arrays.asList("A","B","C"));
digitsMap.put("3",Arrays.asList("D","E","F"));
digitsMap.put("4",Arrays.asList("G","H","I"));
digitsMap.put("5",Arrays.asList("J","K","L"));
digitsMap.put("6",Arrays.asList("M","N","O"));
digitsMap.put("7",Arrays.asList("P","Q","R","S"));
digitsMap.put("8",Arrays.asList("T","U","V"));
digitsMap.put("9",Arrays.asList("W","X","Y","Z"));
}
数字转换为字母
首先从用户键盘中输入一串数字，且这组数字必须在0-99的范围内，这里可以通过while循环和正则表达式判断来保证用户输入内容的合法性，将用户输入的数字进行切割，得到一个只包含0-9的数组，在循环中将每个数组元素作为key从HashMap数据中查询出该数字映射的字母集合，之后再次将这些集合添加到一个崭新的List集合中，且该集合元素类型为String数组，这样就能把每个数字对应的字母集合放入到String数组中，然后将其作为数据源传递给递归方法中，进行多数组排列组合操作，返回一个最终排列结果的List集合，最后直接遍历该集合打印数据即可。代码如下：
public static void digitsToLetters(){
System.out.println("Please input digits from 0 to 9:");
//输入按键数字1-9
String digits="";
while(true){
digits=input.next();
if(!digits.matches("[0-9]{1,2}")){
System.out.println("输入不合法！只能输入0-99的数字,请重新输入：");
}else{
break;
}
}
StringBuilder arrInput=new StringBuilder("Input:arr[] ={");
String[] arrStr=digits.split("");
List<String[]> dataList=new ArrayList<String[]>();
for(int i=0;i<arrStr.length;i++){
arrInput.append(arrStr[i]);
if(i<arrStr.length-1){
arrInput.append(",");
}
//先将多个list中的数据都添加到同一个集合中作为数据源
List<String> lettersList=digitsMap.get(arrStr[i]);
if(lettersList.size()>0){//没有数据的集合不能强行转换为数组
String[] letterArr= (String[]) lettersList.toArray();
dataList.add(letterArr);
}
}
arrInput.append("}");
//递归实现多数组排列组合，并返回最终的排列集合
List<String[]> resultList= makeupLetters(dataList,0,null);
//打印输入内容
System.out.println(arrInput.toString());
System.out.print("Output:");
//打印输出排列组合结果
for(int i=0;i<resultList.size();i++){
String[] letterArr=resultList.get(i);
System.out.print(" ");
for(String s: letterArr){
System.out.print(s);
}
}
}
递归实现多数组排列组合
在递归方法中，我们需要传入需要包含多数组的数据源集合，当前递归的数组在集合中的索引位置以及返回的排列结果集合，在方法中对数组进行遍历，通过复制数组进入扩容和增加新元素，并添加到结果集合中，然后再次递归调用自身方法，每递归一次集合索引位置加1，直到遍历完最后一个数组才返回最终的排列结果集合。代码如下：
private static List<String[]> makeupLetters(List<String[]> dataList, int index, List<String[]> resultList){
if(index==dataList.size()){
return resultList;
}
List<String[]> resultList0=new ArrayList<String[]>();
if(index==0){//第一列数组默认有多少个字母就添加多少个排列数据
String[] dataArr=dataList.get(0);
for(String s : dataArr){
resultList0.add(new String[]{s});
}
}else{
String[] dataArr=dataList.get(index);
for(String[] dataArr0: resultList){
for(String s : dataArr){
//复制数组并扩充新元素
String[] dataArrCopy=new String[dataArr0.length+1];
System.arraycopy(dataArr0, 0, dataArrCopy, 0, dataArr0.length);
dataArrCopy[dataArrCopy.length-1]=s;
//追加到结果集
resultList0.add(dataArrCopy);
}
}
}
return makeupLetters(dataList,++index,resultList0);
}
网友评论