java语言---- 电话号码的字母组合

不念不忘少年蓝@ 2022-02-01 17:51 296阅读 0赞

最近遇到个挺有意思的算法题，题目不是很难，主要考察的是递归，题目是这样的：

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDIyNTYxMw_size_16_color_FFFFFF_t_70]

示例:

输入：“23”  
输出：\[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”\].  
说明:  
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

题目中的数字和字母的对应分为两种情况，一种是如果是7和9的话对应四个字母，如果是其他的数字则对应三个字母，一开始给一个数字的字符串，然后去组合字母，首先应该考虑到使用map去存放数字和字母的对应关系，其次既然是一个字符串包含多个数字并且给的字符串的长度是不确定的，所以应该使用递归循环的策略，代码如下：

class Solution {
    public List<String> letterCombinations(String digits) {
        
        
        if(digits.equals("")){//如果是空串直接返回空的list
            
            return new ArrayList<String>();
            
        }
        
        Map<Character,String> map=new HashMap<Character,String>();
        
        map.put('2',"abc");
        map.put('3',"def");
        map.put('4',"ghi");
        map.put('5',"jkl");
        map.put('6',"mno");
        map.put('7',"pqrs");
        map.put('8',"tuv");
        map.put('9',"wxyz");
        List<String> list=new ArrayList();//用来存放生成的字符串
        
        getStr(map,list,"",digits,0);
        
            
        return list;
        
        
    }
    
    public  String getStr(Map map,List<String> list,String str,String digits,int len){
        
          if(digits.length()!=len){
              
             if(String.valueOf(digits.charAt(len)).equals("7")||String.valueOf(digits.charAt(len)).equals("9")){
    
                for(int i=0;i<4;i++){
    
    
                    str=str+String.valueOf(((String) map.get(digits.charAt(len))).charAt(i));
                     
                    str=getStr(map,list,str,digits,len+1);
                    
                }
            
           }else{
                 
                 
                   for(int i=0;i<3;i++){
                       
                       str=str+String.valueOf(((String) map.get(digits.charAt(len))).charAt(i));
                     
                       str=getStr(map,list,str,digits,len+1);
                    
                   }
              
               
                 
            }
              
              return str.equals("")? "":str.substring(0,len-1);//返回的是一层遍历结束以后对应的上一层的起始字符串
        
         }else {
              
              
              list.add(str);
        
              return str.substring(0,str.length()-1);//返回该层的起始字符串
                  
          
          }
        
    }
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDIyNTYxMw_size_16_color_FFFFFF_t_70]: /images/20220126/f97d705b759147e897e81f2b4ad72074.png