# 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.

![](https://upload.wikimedia.org/wikipedia/commons/thumb/7/73/Telephone-keypad2.svg/200px-Telephone-keypad2.svg.png)

 

**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:

你需要先看前文 [回溯算法详解](https://labuladong.github.io/article/fname.html?fname=%E5%9B%9E%E6%BA%AF%E7%AE%97%E6%B3%95%E8%AF%A6%E8%A7%A3%E4%BF%AE%E8%AE%A2%E7%89%88) 和 [回溯算法团灭子集、排列、组合问题](https://labuladong.github.io/article/fname.html?fname=%E5%AD%90%E9%9B%86%E6%8E%92%E5%88%97%E7%BB%84%E5%90%88)，然后看这道题就很简单了，无非是回溯算法的运用而已。

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

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

###