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 digit 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'].

Solution:

你需要先看前文 回溯算法详解 和 回溯算法团灭子集、排列、组合问题，然后看这道题就很简单了，无非是回溯算法的运用而已。

组合问题本质上就是遍历一棵回溯树，套用回溯算法代码框架即可。

class Solution {
    
    private Map<Integer, String> charMap;
    private List<String> res;
    public List<String> letterCombinations(String digits) {
        
        res = new ArrayList<>();
        if(digits == null || digits.length() == 0)
        {
            return res;
        }
        charMap = buildMap();
        StringBuilder sb  = new StringBuilder();
        dfs(digits, 0, sb);
        return res;
    }
    
    public Map<Integer, String> buildMap()
    {
        Map<Integer, String> res = new HashMap<>();
        res.put(2, "abc");
        res.put(3, "def");
        res.put(4, "ghi");
        res.put(5, "jkl");
        res.put(6, "mno");
        res.put(7, "pqrs");
        res.put(8, "tuv");
        res.put(9, "wxyz");
        return res;
    }
    
    public void dfs(String digits, int start, StringBuilder sb)
    {
        if (start == digits.length())
        {
            res.add(sb.toString());
            return;
        }
        
        String currentChar = charMap.get(digits.charAt(start) - '0');
        for(char c : currentChar.toCharArray())
        {
            sb.append(c);
            dfs(digits, start+1, sb);
            sb.deleteCharAt(sb.length()-1);
        }
    }
    
}