17. Letter Combinations of a Phone Number.md

17. Letter Combinations of a Phone Number

Question:

Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters.

Example:

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

Thinking:

• Method1: 使用了循环，进行二维的遍历。

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> result = new LinkedList<>();
        if(null != digits && digits.length() == 0) return result;
        result.add("");
        String[] d = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

        int len = digits.length();
        for(int i = 0; i < len; i++){
            List<String> tempResult = new LinkedList<>();
            String current = d[new Integer("" + digits.charAt(i))];
            int tempLenth = current.length();
            for(String s : result){
                for(int j = 0; j < tempLenth; j++)
                    tempResult.add(s + current.charAt(j));
            }
            result = tempResult;
        }
        return result;
    }
}

二刷

二刷的时候回溯已经掌握的较为熟练，直接上回溯的套路。

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> result = new LinkedList<>();
        if(digits == null || digits.length() == 0) return result;
        String[] map = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        backtracing(digits, new StringBuilder(), map, 0, result);
        return result;
    }
    private void backtracing(String digits, StringBuilder temp, String[] map, int index, List<String> result){
        if(index == digits.length()){
            result.add(temp.toString());
            return;
        }else{
            String cur = map[digits.charAt(index) - '0'];
            char[] arr = cur.toCharArray();
            for(char c : arr){
                backtracing(digits, temp.append(c), map, index + 1, result);
                temp.deleteCharAt(index);
            }
        }
    }
}

Third time

class Solution {
    public List<String> letterCombinations(String digits) {
        String[] letters = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        List<String> res = new LinkedList<>();
        if(digits == null || digits.length() == 0) return res;
        dfs(digits, 0, res, letters, new StringBuilder());
        return res;
    }
    private void dfs(String digits, int index, List<String> result, String[] letters, StringBuilder sb){
        if(index >= digits.length()){
            result.add(sb.toString());
            return;
        }
        int i = digits.charAt(index) - '0';
        for(int j = 0; j < letters[i].length(); j++){
            sb.append(letters[i].charAt(j));
            dfs(digits, index + 1, result, letters, sb);
            sb.deleteCharAt(index);
        }
    }
}

Fourth Time

• Method 1: dfs

   class Solution {
   	private static final String[] vals = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
   	private List<String> result;
   	public List<String> letterCombinations(String digits) {
   		this.result = new ArrayList<>();
   		if(digits.length() == 0) return this.result;
   		dfs(digits, 0, "");
   		return result;
   	}
   	private void dfs(String digits, int cur, String temp){
   		if(cur == digits.length()){
   			result.add(temp);
   		}else{
   			int num = digits.charAt(cur) - '0';
   			for(char c : vals[num].toCharArray()){
   				dfs(digits, cur + 1, temp + c);
   			}
   		}
   	}
   }

C++ version

• Method 1: recursion

   class Solution {
   private:
   	vector<string> res_;
   	string key[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
   public:
   	vector<string> letterCombinations(string digits) {
   		if(digits.empty()) return res_;
   		recursion(digits, "", 0);
   		return res_;
   	}
   	void recursion(string s, string cur, int index){
   		if(index == s.length()) res_.emplace_back(cur);
   		else{
   			string letters = key[s[index] - '0'];
   			for(const char c: letters){
   				recursion(s, cur + c, index + 1);
   			}
   		}
   	}
   };