电话号码的字母组合

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

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

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

方法：回溯

算法思路：

  1. 确定递归函数的返回值以及参数

    除了题中输入的digits,还需要定义参数index来记录遍历到digits的第几个数字了，以及需要创建一个数组numString用来记录每个数字对应的字母。

    String[] numString = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

  2. 确定终止条件

    当index等于输入数字的个数digits.size()时，收集结果，结束递归。

    if(index == digits.length()){
        result.add(sb.toString());
        return;
    }

  3. 单层搜索的过程

    读取index指向的数字，并找到对应的字符集，然后使用for循环来处理这个字符集（遍历字符集的每个字母）。

    for(int i = 0; i < str.length(); i++){
                sb.append(str.charAt(i));
                backTracking(digits, numString, index + 1);
                sb.deleteCharAt(sb.length() - 1);
            }

代码实现：

class Solution {
    public List<String> result = new ArrayList<>();

    public List<String> letterCombinations(String digits) {
        if(digits == null || digits.length() == 0)return result;
        String[] numString = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        backTracking(digits, numString, 0);
        return result;
    }

    StringBuilder sb = new StringBuilder();

    public void backTracking(String digits, String[] numString, int index){
        if(index == digits.length()){
            result.add(sb.toString());
            return;
        }
        String str = numString[digits.charAt(index) - '0'];
        for(int i = 0; i < str.length(); i++){
            sb.append(str.charAt(i));
            backTracking(digits, numString, index + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

参考

代码随想录 - 电话号码的字母组合