# Letter Combinations of a Phone Number

show

## Problem Statement

Given a digit string, return all possible letter combinations that the number could represent. A mapping of digits to letters (just like on the telephone buttons) is given below.

The digit 0 maps to 0 itself.
The digit 1 maps to 1 itself.

Examples:
Input: Digit = “23”
Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
Explanation:   The list shows the different possible combinations of the strings possible.

• “ad” – Press digit 2 once, digit 3 once.
• “ae”-   Press digit 2 once, digit 3 twice
• “af” –  Press digit 2 twice, digit 3 once, and so on.

Input:   Digit = “2”
Output: [“a”, “b”, “c”]

## Approach: Backtracking

The problem can be solved using the backtracking approach. The idea is to consider a digit as the starting point and generate all possible combinations with that letter. Check the below illustration for a better understanding.

Algorithm

• If the input is empty, simply return an empty array.
• Initialize a hashmap that maps digits to their letters, i.e. mapping “2” to “a”, “b”, and “c”.
• Consider a backtracking function for generating all possible combinations:
• Consider the parameters of the backtracking function as the path, i.e the current path we are traversing on and the index, i.e. on the digit we are on.
• The base case would be, if our current combination of letters is the same length as the input digits, that iteration is complete. Therefore, insert it into the answer list, and backtrack.
• Else, find all the possible combinations of letters that correspond with the current digit i.e. digits[index].
• Traverse through the letters. For each letter, insert the letter to our current path, and backtrack again, and increment the index by 1.
• Remove the letter from the path once the iteration is completed.

### C++ Code

```class Solution {
public:
vector < string > letterCombinations(string digits) {
if (!digits.size()) {
return {};
}

vector < string > combs;
const vector < string > chars = {
"0",
"1",
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz"
};
string builder;
build(builder, 0, digits, chars, combs);
return combs;
}
void build(string builder, int i,
const string & digits,
const vector < string > & chars, vector < string > & combs) {
if (i == digits.size()) {
combs.push_back(builder);
return;
}

int d = digits[i] - '0';
for (char ch: chars[d]) {
build(builder + ch, i + 1, digits, chars, combs);
}
}
};```

### Java Code

```class Solution {
private List < String > combinations = new ArrayList < > ();
private Map < Character, String > letters = Map.of(
'2', "abc", '3', "def", '4', "ghi", '5', "jkl",
'6', "mno", '7', "pqrs", '8', "tuv", '9', "wxyz");
private String phoneDigits;

public List < String > letterCombinations(String digits) {
if (digits.length() == 0) {
return combinations;
}
phoneDigits = digits;
backtrack(0, new StringBuilder());
return combinations;
}

private void backtrack(int index, StringBuilder path) {
if (path.length() == phoneDigits.length()) {
return;
}
String possibleLetters = letters.get(phoneDigits.charAt(index));
for (char letter: possibleLetters.toCharArray()) {
path.append(letter);
backtrack(index + 1, path);
path.deleteCharAt(path.length() - 1);
}
}
}```

### Python Code

```class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if len(digits) == 0:
return []

letters = {
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz",
}

def backtrack(index, path):
if len(path) == len(digits):
combinations.append("".join(path))
return

possible_letters = letters[digits[index]]
for letter in possible_letters:

path.append(letter)

backtrack(index + 1, path)

path.pop()

combinations = []
backtrack(0, [])
return combinations```

Time Complexity: O(4^N * N), where N is the length of a digit string
Space Complexity: O(N)

Practice ProblemLetter Phone

## FAQs

Q. How does the backtracking function work?
A. The backtracking approach is to consider a digit as the starting point and generate all possible combinations with that letter. The base case would be, if our current combination of letters is the same length as the input digits, that iteration is complete. Therefore, insert it into the answer list, and backtrack. Else, find all the possible combinations of letters that correspond with the current digit i.e. digits[index].

Q. What is the time complexity and space complexity of the backtracking approach?
A. The time complexity of the backtracking approach is O(4^N * N) and space complexity is O(N).

##### Previous Post ## 7 Best PHP IDE & Source Code Editors 

##### Next Post 