17. 电话号码的字母组合

佚名 6年前 (2019-05-13) 随笔 1501人围观抢沙发百度已收录

题目描述

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

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

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

示例:

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

说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

分析

DFS + 回溯的思路，穷举出所有可能，并加入list中。
执行用时 : 1 ms, 在Letter Combinations of a Phone Number的Java提交中击败了99.94% 的用户
内存消耗 : 35.2 MB, 在Letter Combinations of a Phone Number的Java提交中击败了86.40% 的用户

贴出代码

class Solution {
    private String[] arr = new String[]{"0","1","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    public List<String> letterCombinations(String digits) {
        List<String> list = new ArrayList<>();
        if(digits != null  && digits.length() > 0){
            dfs(list, digits,0,"");
        }
        return list;
    }
    
    public void dfs(List<String> list,String digits, int d, String str){
        if(d == digits.length()){
            list.add(str);
            return;
        }
        for(int i = 0 ; i < arr[digits.charAt(d) - '0'].length(); i ++){
            dfs(list,digits,d + 1,str + arr[digits.charAt(d) - '0'].charAt(i));
        }
    }
}