2014年5月12日星期一

Recursive Solution - Letter Combinations of a Phone Number

A map is created to store the relations between numbers and Strings. Other than this, it is a typical recursive approach.

public class Solution {
    Map<Character, String> keyboards = new HashMap<Character, String>();
   
    public ArrayList<String> letterCombinations(String digits) {
       
        ArrayList<String> results = new ArrayList<String>();
       
        if(digits == null || digits.length() == 0){
            results.add(""); //guarantee results is not null/empty.
            return results;
        }
       
        if(keyboards.get('2') == null){
            buildMap();
        }
       
        ArrayList<String> preResults = letterCombinations(digits.length() < 2? null : digits.substring(1));
        String cur = keyboards.get(digits.charAt(0));
        StringBuilder res = new StringBuilder();
        for(int i = 0; i < cur.length(); i++){
            res.delete(0, res.length());
            res.append(cur.charAt(i));
            // if(preResults.size() == 0){
            //     results.add(res.toString());
            // }else{
                for(String preResult : preResults){
                    res.delete(1, res.length());
                    res.append(preResult);
                    results.add(res.toString());
                }
            //}
        }
        return results;
    }
   
    private void buildMap(){
        keyboards.put('2', "abc");
        keyboards.put('3', "def");
        keyboards.put('4', "ghi");
        keyboards.put('5', "jkl");
        keyboards.put('6', "mno");
        keyboards.put('7', "pqrs");
        keyboards.put('8', "tuv");
        keyboards.put('9', "wxyz");
        keyboards.put('0', " ");
    }
}

没有评论: