Thursday, October 10, 2013

Letter Combinations of a Phone Number

Q:
Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.
A:
 -----------------------3 rd ------递归调用-------  作者-对于digits=""的情况跟我们假设的不一样------------最新版本的改了。------

public class Solution {
    public List<String> letterCombinations(String digits) {
        // assume all chars in digits are in 2 to 9
        List<String> list = new LinkedList<String>();
        if(digits.length() == 0) {
            list.add("");
            return list;
        }
        HashMap<Character,String> map = new HashMap<Character,String>();
        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");
        return helper(map,digits);
    }
    public List<String> helper(HashMap<Character, String> map, String digits){
        List<String> list = new LinkedList<String>();
        String str = map.get(digits.charAt(0));
        if(digits.length() == 1){
            for(int i =0;i<str.length();i++)
                list.add(""+str.charAt(i));
        }else{
            List<String> newList  = helper(map, digits.substring(1));
            for(int i =0;i<str.length();i++)
                for(String tmp:newList)
                    list.add(str.charAt(i)+tmp);
        }
        return list;
    }
}



--------见最后面----

Mistakes:
1: 将al,加入到all中的时候,  没有考虑当all为空的时候。 导致all一直为空。
2: given input as "", we expect the value [""] ,    这个,好像是因为, 作者的实现方法和我们的不一样,因此,我们这里,需要多处理一下。 呵呵 ------------ 以后问明白了。 这种边边角角的情况。


--------------------------------2 nd Pass-------------------------
Mistakes: 
1:   这里,应该算是题意给的不太对。

public class Solution {
    public List<String> letterCombinations(String digits) {
        Map<Character, String> map = new HashMap<>();
        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> res = new LinkedList();
        if(digits.length()==0)
            return res;
        res.add("");// this is the base case for 0 length
        for(int i =0;i<digits.length();i++){
            List<String> res2 = new LinkedList();
            String str = map.get(digits.charAt(i));
            for(String ss : res)
                for(char ch : str.toCharArray())
                    res2.add(ss+ch);
            res = res2;
        }
        return res;
    }
}

No comments:

Post a Comment