class Solution {
    String[] mapping=new String[]{"0","1","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    List<String> list=new LinkedList();
    public List<String> letterCombinations(String digits) {
        if(digits==null || digits.length()==0) return list;
        dfs(digits,0,"");
        return list;
    }

    void dfs(String s,int pos,String res){
        if(pos==s.length()){
            list.add(res);
        }else{
            int num=s.charAt(pos)-'0';
            String mapStr=mapping[num];
            for(int i=0;i<mapStr.length();i++){
                char c=mapStr.charAt(i);
                dfs(s,pos+1,res+c);
            }
        }
    }
}