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

经典回溯题了
写回溯要注意下面几个关键点：
-> 1、递归终止条件
-> 2、子递归结束后的复原

递归终止条件：已获取的字符长度等于 num 长度

子递归结束后的复原：

接下来就是愉快的编码

public class Solution {

    private static final String[] seq = new String[]{
            "",
            "",
            "ABC",
            "DEF",
            "GHI",
            "JKL",
            "MNO",
            "PQRS",
            "TUV",
            "WXYZ"};

    public ArrayList phoneNumber (String num) {
        ArrayList res = new ArrayList();
        StringBuilder track = new StringBuilder();
        int depth = num.length();
        backtrack(track,res,0,depth,num);
        return res;
    }

    private void backtrack(StringBuilder track,ArrayListres,int currDepth,int maxDepth,String num) {
        if (currDepth>=maxDepth) {
            res.add(track.toString());
            return;
        }
        int index = (int) num.charAt(currDepth) - '0';
        String currSeq = seq[index];
        for (int i = 0; i < currSeq.length(); i++) {
            track.append(currSeq.charAt(i));
            backtrack(track,res,currDepth+1,maxDepth,num);
            track.deleteCharAt(track.length()-1);
        }
    }
}