一、题目
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
二、解法
思路:很经典的回溯思想。
要注意的点:String和StringBuffer的选择。
- String内的值不可变(final),如果多次更改String的值,实际上是新创建了一个String,然后将新创建的String地址赋给原变量,这样会导致内存浪费和GC,使得性能降低。
- StringBuffer和StringBuilder是可以在原地改变字符串的值,通过一些函数比如append(),remove(),delete(),replace()等。区别是StringBuffer是线程安全的,StringBuilder不是线程安全的。
class Solution {
private Map<Integer,String> map=new HashMap<Integer,String>();
public void dfs(List<String> ans,String digits,int idx,StringBuffer cur){
if(idx==digits.length()){
ans.add(cur.toString());
return;
}
String str=map.get(Character.getNumericValue(digits.charAt(idx)));
for(int i=0;i<str.length();++i){
cur.append(str.charAt(i));
dfs(ans,digits,idx+1,cur);
cur.deleteCharAt(cur.length()-1);
}
}
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");
List<String> ans=new ArrayList<String>();
if(digits.length()==0){
return ans;
}
dfs(ans,digits,0,new StringBuffer());
return ans;
}
}