电话号码的数字组合(Java)
思路是利用回溯解决,注意回溯的返回条件即可。
class Solution {
List<String> list=new ArrayList();
Map<String,String> map=new HashMap();
public List<String> letterCombinations(String digits) {
map.put("2","abc");
map.put("3","def");
map.put("4","ghi");
map.put("5","jkl");
map.put("6","mno");
map.put("7","pqrs");
map.put("8","tuv");
map.put("9","wxyz");
if(digits.length()!=0)
BackTrack("",digits);
return list;
}
public void BackTrack(String already,String next){
if(next.length()==0)
list.add(already);
else{
String key=next.substring(0,1);
String value=map.get(key);
for(int i=0;i<value.length();i++){
String s=already+value.substring(i,i+1);
BackTrack(s,next.substring(1));
}
}
}
}