/*
题目：电话号码的字母组合 middle
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序
思路：
dfs
*/
package leetCode.Other;import java.util.ArrayList;
import java.util.List;public class lc_dfs_17_letterCombinations {public static void main(String[] args) {lc_dfs_17_letterCombinations m = new lc_dfs_17_letterCombinations ();m.letterCombinations("22");}public List<String> letterCombinations(String digits) {if (digits == null || digits.length() == 0)return res;String[][] list = {{"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"},};dfs(list, new StringBuilder(), digits.toCharArray(), 0, 0);
// System.out.println(res);return res;}List<String> res = new ArrayList<>();/**** @param list charArr[i]对应映射的字典* @param sb* @param charArr digit转化的字符数组* @param charArrIndex 当前遍历的charArr的下标* @param depth 当前遍历的charArr的长度*/public void dfs(String[][] list, StringBuilder sb, char[] charArr, int charArrIndex, int depth) {//当达到charArr的长度时，表示已递归结束if (depth == charArr.length) {res.add(sb.toString());return;}// 得到对应list里的映射下标，charArr最小是2，对应list的0int listIndex = charArr[charArrIndex] - '0' - 2;
// 遍历charArr[charArrIndex]映射的listfor (int i = 0; i < list[listIndex].length; i++) {sb.append(list[listIndex][i]);
// 每追加一个映射的字符，就跳到charArr下一个字符，深度+1dfs(list, sb, charArr, charArrIndex + 1, depth + 1);
// 递归完，该层将追加的映射字符删除，重新追下下一个可能的映射字符sb.deleteCharAt(sb.length() - 1);}}
}