17. 电话号码的字母组合

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例.png

2对应abc      3对应def  ...  9对应wxyz

分析:
其实就是给定一个数字组合的字符串，让我们转换成对应的所有字母组合排列；
有一个隐形条件就是虽然一个数字对应的是多个字母，但一次只能拿出一个字母来配对，就像电话按键输入一样

思路：

考虑使用DFS(Depth-first search 深度优先搜索)来解决此类问题，很多排列组合相关的问题，都可以通过DFS来解决

class Solution {

    private char[] cs;//字符数组
    private List<String> list;//最终存放字符组合的数组
    //记录每一层选择的字母，一趟结束后再转成字符串就是一个字母组合咯
    private char[] strings;
    //数字字母对照表
    private char[][] lettersArray = {
       {'a','b','c'},{'d','e','f'},{'g','h','I'},
       {'j','k','l'},{'m','n','o'},{'p','q','r','s'},
       {'t','u','v'},{'w','x','y','z'}
    };

    public List<String> letterCombinations(String digits) {
       
       //1.字符串为空 没有意义
       if(digits == null) return null;
 
       //1.1 定义一个最终存放字符组合的数组
       list = new ArrayList<>();
       //1.2 转字符数组
       cs = digits.toCharArray();
       //1.3 digits是空字符，直接返回 list
       if(cs.length==0) return list;
       //1.4 字母组合数组的长度和cs等长即可
       strings = new char[cs.length];

       //2. 搜索字母组合
       dfs(0);

       //3. 返回字符组合的数组
       return list;

    }

    //私有 没有返回值 深度优先搜索
    //idx: 正在搜索第idx层
    private void dfs(int idx) {

        //1.已经进入最后一层了 不能再深入 存起来得到的值
        if(idx==cs.length) {
            //得到一个正确的解，就添加到数组中
            list.add(new String(strings));
            return;
        }

       //数字字符
       char digit = cs[idx];
       //数字字符减去'2'就是对应索引 (2~0  3~1 4~2 ...) 就得到  所有能选择的字母
       char[] letters = lettersArray[digit - '2'];
       //2. 先枚举这一层可以做的所有选择
       for(char letter : letters){
        //取出其中一个字符记录下来
         strings[idx] = letter;
         //下一层 自动回溯
         dfs(idx + 1);

       }

    }

}

执行结果.png