17. Letter Combinations of a Phone Number ---M

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

 

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = ""
Output: []

Example 3:

Input: digits = "2"
Output: ["a","b","c"]

 

Constraints:

• 0 <= digits.length <= 4
• digits[i] is a digit in the range ['2', '9'].

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:   这里，应该算是题意给的不太对。

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> res;
        if(digits.length()==0)
            return res;
        res.emplace_back("");
        unordered_map<char, string> M;
        M['2']="abc";
        M['3']="def";
        M['4']="ghi";
        M['5']="jkl";
        M['6']="mno";
        M['7']="pqrs";
        M['8']="tuv";
        M['9']="wxyz";
        for(auto ch : digits){
            auto str = M[ch];
            vector<string> newRes;
            for(string s: res){
                for(char ch: str ){
                    newRes.emplace_back(s+ch);
                }
            }
            res = newRes;
        }
        return res;
    }
};