电话号码的字母组合

题目描述

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

示例:

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

public class App {
    //  全排列问题

    public static void main(String[] args) {

        letterCombination("23");
    }

    /**
     *  str 需要转换的数字
     *  Letter Combinations of a Phone Number
     */
    private static void letterCombination(String str) {

        if (str.isEmpty()){
            return;
        }
        String[] dict = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
        String path = "";

        letterCombination(str,dict,0,path);

    }
    /**
     *  str 需要转换的数字
     *  dict 转换字典
     *  index str的下标 也就是当前选择的char
     *  path 存储结果
     */
    private static void letterCombination(String str,String[] dict, int index,String path) {
        // 结束条件  index 到达 str尾部可选最后一个字母 再往后移无可选数字
        // str = 23 index = 0 时选'2'; index = 1 时选'3'; index = 2 无选择
        if (str.length() == index){
            System.out.println(path);
        }else {
            // 取str 中的char 转为数字
            int num = str.charAt(index) - '0';
            // dict[num] 是一个字符串
            for (int i=0;i< dict[num].length(); i++){
                // 选择
                path = path + dict[num].charAt(i);
                letterCombination(str,dict,index+1,path);
                // 撤销选择
                path = path.substring(0,path.length()-1);
            }
        }

    }
}