# LeetCode 17. Letter Combinations of a Phone Number

## Description

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"


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

## Explanation

First, build a map that stores relationships between numbers and the letters they represent.

Then, use backtracking approach to generate all possible combinations.

## Java Solution

class Solution {
public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();

if (digits == null || digits.equals("")) {
return result;
}

StringBuilder sb = new StringBuilder();

Map<Character, char[]> lettersMap = getLettersMap();

letterCombinationsHelper(digits, sb, lettersMap, result);

return result;
}

private Map<Character, char[]> getLettersMap() {
Map<Character, char[]> lettersMap = new HashMap<>();
lettersMap.put('0', new char[]{});
lettersMap.put('1', new char[]{});
lettersMap.put('2', new char[]{'a', 'b', 'c'});
lettersMap.put('3', new char[]{'d', 'e', 'f'});
lettersMap.put('4', new char[]{'g', 'h', 'i'});
lettersMap.put('5', new char[]{'j', 'k', 'l'});
lettersMap.put('6', new char[]{'m', 'n', 'o'});
lettersMap.put('7', new char[]{'p', 'q', 'r', 's'});
lettersMap.put('8', new char[]{'t', 'u', 'v'});
lettersMap.put('9', new char[]{'w', 'x', 'y', 'z'});

return lettersMap;
}

private void letterCombinationsHelper(String digits, StringBuilder sb, Map<Character, char[]> lettersMap, List<String> result) {
if (sb.length() == digits.length()) {
return;
}

for (char ch : lettersMap.get(digits.charAt(sb.length()))) {
sb.append(ch);
letterCombinationsHelper(digits, sb, lettersMap, result);
sb.deleteCharAt(sb.length() - 1);
}
}
}

## Python Solution

class Solution:
def letterCombinations(self, digits: str) -> List[str]:
results = []

if not digits:
return results

mapping = {
"2": ["a", "b", "c"],
"3": ["d", "e", "f"],
"4": ["g", "h", "i"],
"5": ["j", "k", "l"],
"6": ["m", "n", "o"],
"7": ["p", "q", "r", "s"],
"8": ["t", "u", "v"],
"9": ["w", "x", "y", "z"]
}

self.helper(results, "", digits, mapping)

return results

def helper(self, results, combination, digits, mapping):
if digits == "":
results.append(combination)
return

letters = mapping[digits[0]]

for letter in letters:
combination += letter
self.helper(results, combination, digits[1:], mapping)
combination = combination[:-1]
• Time complexity: O(3^N×4^M) where N is the number of digits in the input that maps to 3 letters (e.g. 2, 3, 4, 5, 6, 8) and M is the number of digits in the input that maps to 4 letters (e.g. 7, 9), and N+M is the total number digits in the input.
• Space complexity: O(3^N×4^M) since one has to keep 3^N \times 4^M solutions.

## 3 Thoughts to “LeetCode 17. Letter Combinations of a Phone Number”

1. Noman says:

bro i am not good at recursion . Could you please explain it in betterways? how sb.length works here or how the combinations is happening???

2. Lawrence says:

Hello, how can I reach you privately?
my email is ljustincoder@gmail.com. I need help in understanding some of your solutions.
Secondly, regarding the letter combinations of a phone number. I understand what your code does but my recursion skill is weak and need clarity on one condition. So, say digit is “23”. the first time the helper is called. sb is “”. but what is the index of “”? how did the computer know that when you do :
lettersMap.get(digits.charAt(sb.length())), it is to get the the index 2? is “” equated to 0?

then, it gets the first character in the key 2 and appends it to the StringBuilder making the sb.length=1. Ok. I get it, it picks the map with key index 1 which is 3 and begins to add its’ characters. and each time the sb.length==digit.length, it adds the StringBuilder to the result list. and then removes that character. it continues until even the character a from the phone number 2 is removed, defaulting the StringBuilder sb to “” again. at this stage, the result is “ad, ae, af”.
Now, this is where I don’t understand it. Because instead of picking character a again, it picks b. how was the programme able to know that the first character in phone number key 2, which is ‘a’ should be overlooked?

This is what I don’t get.

Lastly, have you considered setting up a patron page where people like me can donate something, no matter how small, to encourage you? I am glued to your youtube videos and seriously testing the codes to make sense of your thought processes. Please, don’t stop. You are the only one explaining it simplistically. Is there a way to also send you Leetcode questions I find challenging so you can solve and explain to the community?