LeetCode 17. 电话号码的字母组合

Love The Way You Lie 2022-10-27 02:48 173阅读 0赞

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

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

![在这里插入图片描述][ae1f9e931c60f753b50176ec16537070.png_pic_center]

示例 1：
    
    输入：digits = "23"
    输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
    示例 2：
    
    输入：digits = ""
    输出：[]
    示例 3：
    
    输入：digits = "2"
    输出：["a","b","c"]
     
    
    提示：
    
    0 <= digits.length <= 4
    digits[i] 是范围 ['2', '9'] 的一个数字。
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：简单的深度优先搜索即可。

class Solution {
        
       String alpha[]=new String[10];
    	public List<String> letterCombinations(String digits) {
        
            List<String> res=new ArrayList<>();
            if(digits.length()==0) return res;
            alpha[2]="abc";
            alpha[3]="def";
            alpha[4]="ghi";
            alpha[5]="jkl";
            alpha[6]="mno";
            alpha[7]="pqrs";
            alpha[8]="tuv";
            alpha[9]="wxyz";
            StringBuffer tmp=new StringBuffer();
            dfs(digits, res, 0, tmp);
            System.out.print(res);
            return res;
        }
        public void dfs(String digits,List<String> res,int index,StringBuffer tmp){
        
            if(index==digits.length()){
        
                res.add(tmp.toString());
                return;
            }
            int num=digits.charAt(index)-'0';
            for(int i=0;i<alpha[num].length();i++) {
        
            	tmp.append(alpha[num].charAt(i));
            	dfs(digits, res, index+1, tmp);
            	tmp.deleteCharAt(tmp.length()-1);
            }
        }
    }

[ae1f9e931c60f753b50176ec16537070.png_pic_center]: /images/20221024/14bdab80079c4ad4a323eb3732313dd5.png