电话号码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num string字符串 
     * @return string字符串ArrayList
     */
    private static final String[] seq = new String[]{
            "",
            "",
            "ABC",
            "DEF",
            "GHI",
            "JKL",
            "MNO",
            "PQRS",
            "TUV",
            "WXYZ"};

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

    private void backtrack(StringBuilder track,ArrayList<String>res,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);
        }
    }
}