import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param num string字符串 * @return string字符串ArrayList */ private char[] chars; /** 用来存储每一层选择的字母 */ private char[] string; private ArrayList<String> list; // 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'} // }; 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 ArrayList<String> phoneNumber(String digits) { if (digits == null) return null; list = new ArrayList<String>(); chars = digits.toCharArray(); if (chars.length == 0) return list; string = new char[chars.length]; dfs2(0); return list; } /** * @param idx 正在搜索第idx层 */ private void dfs2(int idx) { // 已经进入最后一层,不能往下再搜索,封装数据 if (idx == chars.length) { // 得到一个解 list.add(new String(string)); return; } // 枚举这一层能做的所有选择 char[] letters = lettersArray[chars[idx] - '2']; for (char letter : letters) { string[idx] = letter; dfs2(idx + 1); } } }
解题思想:递归,dfs套路,排列组合问题均可适用dfs套路。