# 17 Letter Combinations of a Phone Number

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.

``````   1       2(abc)  3(def)
4(ghi)  5(jkl)  6(mno)
7(pqrs) 8(tuv)  9(wxyz)
*+      0_      ^#
``````

Example 1:

``````Input: digits = "23"
``````

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']`.
 ``````1 2 3 4 5 6 7 8 9 `````` ``````class Solution: def letterCombinations(self, digits: str) -> List[str]: if not digits: return [] M = [0, 1, 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'] res = [''] for c in digits: res = [p+n for p in res for n in M[int(c)]] return res``````
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 `````` ``````func letterCombinations(digits string) []string { if digits == "" { return []string{} } m := map[byte]string{ '0': "0", '1': "1", '2': "abc", '3': "def", '4': "ghi", '5': "jkl", '6': "mno", '7': "pqrs", '8': "tuv", '9': "wxyz", } var res []string backtrack("", &res, 0, digits, m) return res } func backtrack(cur string, res *[]string, i int, digits string, m map[byte]string) { if i == len(digits) { *res = append(*res, cur) return } for _, c := range m[digits[i]] { backtrack(cur+string(c), res, i+1, digits, m) } }``````
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 `````` ``````class Solution { public static Map M = Map.of( "2", "abc", "3", "def", "4", "ghi", "5", "jkl", "6", "mno", "7", "pqrs", "8", "tuv", "9", "wxyz"); public List letterCombinations(String digits) { ArrayList res = new ArrayList<>(); if (digits.length() == 0) { return res; } backtrack("", 0, digits, res); return res; } private void backtrack(String cur, int i, String digits, List res) { if (i == digits.length()) { res.add(cur); } else { String chars = M.get(String.valueOf(digits.charAt(i))); for (char c : chars.toCharArray()) { backtrack(cur+c, i+1, digits, res); } } } }``````