leetcode17. 电话号码的字母组合-小羊的记录本

17. 电话号码的字母组合
    字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
    
    示例:

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

思路：
1.回溯法，适用于树状结构；
2.回溯参数确定，backtrack(输入字符串，输出字符串，位置)

代码

class Solution {
	List<String> ans=new ArrayList<>();
	public List<String> letterCombinations(String digits) {
		String[] map={"","*","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
		backtrack(digits,ans,0);
		return ans;
	}
	public List<String> backtrack(String digits,String letter,int index){
		if(index==digit.length()){
			ans.add(letter);
			return ans;
		}
		char c=digits.charAt(index);//2,3
		int pos=c-'0';//2,3
		String curr_str=map[pos];//abc,def
		for(int i=0;i<curr_str.length();i++){
			backtrack(digits,ans+curr_str.charAt(i),index+1);
		}
	}
	return ans;
}