电话号码的字母组合

原题链接

使用的方法

回溯算法

解题思路

• 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。数字到字母的映射与电话按键相同。注意 1 不对应任何字母。
• 我们可以使用回溯算法来生成所有可能的字母组合。回溯算法是一种系统地搜索所有可能的解决方案的方法。在这个问题中，我们可以通过递归地构建字母组合来生成所有的组合。
• 我们从空字符串开始，逐步添加数字对应的字母来构建字母组合。在每一步，我们根据当前数字获取对应的字母，然后递归地探索每个字母的组合。通过递归地探索这些选择，我们可以生成所有可能的字母组合。
• 递归的终止条件是当我们处理到输入字符串的最后一个数字时，我们将当前的字母组合添加到结果列表中。通过这种方式，我们可以生成所有可能的字母组合，并最终返回结果列表。

代码实现

class Solution {
    private final String[] map = {
        "", //0
        "", //1
        "abc", //2
        "def", //3
        "ghi", //4
        "jkl", //5
        "mno", //6
        "pqrs",//7
        "tuv",//8
        "wxyz"//9
    };
    private List<String> res = new ArrayList<>();

    public List<String> letterCombinations(String digits) {
        if(digits == null) return res;
        
        backTrack(digits,0,"");
        return res;
    }

    public void backTrack(String digits,int index,String path){
        if(index == digits.length()){
            res.add(path);
            return;
        }
        int digit = digits.charAt(index) - '0';
        String letters = map[digit];

        for(int i=0;i< letters.length();i++){
            backTrack(digits,index+1,path + letters.charAt(i));
        }
        return;
    }
}