电话号码的字母组合java实现

题目描述

https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number

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

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:

输入："23" 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

思路：DFS+回溯找所有可能的解，用switch语句判断2-9的字母

class Solution {
    List<String> res=new ArrayList<String>();
    public List<String> letterCombinations(String digits) {
        if(digits==null||digits.length()==0)
        return res;
        String str="";
        dfs(digits,res,0,str);
        return res;
    }
    public void dfs(String digits,List<String> res,int start,String str){
        if(start==digits.length()){//当digits读完，输出
            res.add(str);
            return;
        }
        char c=digits.charAt(start);
        char[] letter=null;//初始化数组
        switch(c){//判断当前数字的字母
            case 2:
            letter=new char[3];
            letter[0]=a;letter[1]=b;letter[2]=c;
            break;
            case 3:
            letter=new char[3];
            letter[0]=d;letter[1]=e;letter[2]=f;
            break;
            case 4:
            letter=new char[3];
            letter[0]=g;letter[1]=h;letter[2]=i;
            break;
            case 5:
            letter=new char[3];
            letter[0]=j;letter[1]=k;letter[2]=l;
            break;
            case 6:
            letter=new char[3];
            letter[0]=m;letter[1]=n;letter[2]=o;
            break;
            case 7:
            letter=new char[4];
            letter[0]=p;letter[1]=q;letter[2]=r;letter[3]=s;
            break;
            case 8:
            letter=new char[3];
            letter[0]=t;letter[1]=u;letter[2]=v;
            break;
            case 9:
            letter=new char[4];
            letter[0]=w;letter[1]=x;letter[2]=y;letter[3]=z;
            break;
            default:
        }
        for(int i=0;i<letter.length;i++){
            //DFS，str+letter[i]不对str操作因此不用回退
            dfs(digits,res,start+1,str+letter[i]);
        }
    }
}