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

import java.util.*;


public class Solution {

    ArrayList<String> ret;
    StringBuilder path ;
    String[] hash = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    //存储数字与字母的映射关系
    public ArrayList<String> phoneNumber (String num) {
        // write code here
        ret = new ArrayList<>();
        path = new StringBuilder();
        dfs(num,0);
        return ret;
    }

    public void dfs(String num,int pos){
        //递归子函数,pos记录翻译到了能够数字
        if(pos==num.length()){
            //递归到了叶子节点
            ret.add(new String (path));
            return;
        }
        
        
        //得到当前数字对应的字符，递归加入该字符
        String cur = hash[num.charAt(pos)-'0'];
        //遍历每个字母，因为第一次有三种选择
        for(int i=0;i<cur.length();i++){
            //将该字符加入path
            path.append(cur.charAt(i));
            //dfs下一个数字
            dfs(num,pos+1);

            //回溯
            path.deleteCharAt(path.length()-1);
        }

    }
}