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);
        }
    }
}

Amazon session

class Solution {
    private static final String[] letters = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    private List<String> res;
    public List<String> letterCombinations(String digits) {
        this.res = new ArrayList<>();
        if(digits.length() == 0) return res;
        dfs(digits, 0, new StringBuilder());
        return this.res;
    }
    private void dfs(String digits, int index, StringBuilder sb){
        if(index == digits.length()) res.add(sb.toString());
        else{
            char[] arr = letters[digits.charAt(index) - '0'].toCharArray();
            for(char c : arr){
                sb.append(c);
                dfs(digits, index + 1, sb);
                sb.deleteCharAt(sb.length() - 1);
            }
        }
    }
}