题解 | #电话号码的字母组合#

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套路。