leetcode 17. 电话号码的字母组合

一、题目

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
leetcode 17. 电话号码的字母组合

二、解法

思路:很经典的回溯思想。

要注意的点: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;
    }
}
上一篇:Leetcode —— 17. 电话号码的字母组合(Java)


下一篇:LeetCode - 解题笔记 - 66 -Plus One