# Solution For Letter Combinations Of A Phone Number

Problem Statement:

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

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

Solution:

This problem can be solved by using the Depth First Search approach. We need to make a recursive call on all possible combinations, using the mapping of digits to characters given by the phone buttons. We will use a hash-map to store the mapping of digits to corresponding characters.

For example,:

• If our input is 2, then the mapping is “abc”, because the digit 2 maps to a, b and c on the phone button.
• If our input is 3, then the mapping is “def”, because the digit 3 maps to d, e and f on the phone button.

We will start by storing all the possible mappings in the hash-map, and then make a recursive call on the first digit’s characters. For each character in this list, we will append it to the result, and then go on to make a recursive call on the next digit’s characters. We will continue this process until we reach the end of the input.

Here’s the algorithm in steps:

1. Create a hash-map to store mappings
2. Define a helper function that takes in two parameters:
3. A string ‘output’ to store all possible combinations
4. An integer ‘index’ representing the current index to process in digits
5. If index == length of digits, append the output to the result and return
6. Find all characters corresponding to ‘digits[index]’ in the hash-map
7. Loop through the characters and recursively call the helper function with:
8. ‘output’ appended with the current character being processed
9. ‘index+1’ as the new index to process in digits
10. Return the result

Pseudo-code:

“`
phoneNumberMap = { ‘2’: ‘abc’, ‘3’: ‘def’, ‘4’: ‘ghi’, ‘5’: ‘jkl’,
‘6’: ‘mno’, ‘7’: ‘pqrs’, ‘8’: ‘tuv’, ‘9’: ‘wxyz’ }

def letterCombinations(digits):
if len(digits) == 0:
return [] result = [] helper(”, 0, digits, result)
return result

def helper(output, index, digits, result):
if index == len(digits):
result.append(output)
return
for char in phoneNumberMap[digits[index]]:
helper(output+char, index+1, digits, result)
“`

Time Complexity:

The time complexity of this algorithm would be O(4^n), where n is the number of digits in the input string. This is because the maximum number of combinations possible with n digits is 4^n (each digit having a maximum of 4 possible characters).

Space Complexity:

The space complexity is O(n), where n is the number of digits in the input string. This is because the maximum depth of the recursion tree would be n, as we are processing one digit at a time.

## Step by Step Implementation For Letter Combinations Of A Phone Number

```public class Solution {
public List letterCombinations(String digits) {
if(digits.isEmpty()) return ans;
String[] mapping = new String[] {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
for(int i =0; idef letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
# define a dictionary that maps digits to letters
digit_letters = {
'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']
}

# base case
if len(digits) == 0:
return []

# recursive case
# we use the first digit to generate all possible letters
# and then we recurse on the remaining digits
first_digit = digits[0]
first_letters = digit_letters[first_digit]
remaining_digits = digits[1:]
remaining_letters = self.letterCombinations(remaining_digits)

# we need to combine the letters from the first digit
# with all the permutations of the remaining letters
combinations = []
for letter in first_letters:
if len(remaining_letters) == 0:
combinations.append(letter)
else:
for remaining_letter in remaining_letters:
combinations.append(letter + remaining_letter)

return combinationsvar letterCombinations = function(digits) {
if (digits.length === 0) {
return [];
}
const phone = {
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']
};
let result = phone[digits[0]];
// for each remaining digit, we take the result so far
// and add each possible letter to each element
for (let i = 1; i < digits.length; i++) {
const letters = phone[digits[i]];
const temp = [];
for (let j = 0; j < letters.length; j++) {
for (let k = 0; k < result.length; k++) {
temp.push(result[k] + letters[j]);
}
}
result = temp;
}
return result;
};vector letterCombinations(string digits) {
vector result;
if (digits.empty()) return result;
static const vector v = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
result.push_back("");   // add a seed for the initial case
for (int i = 0 ; i < digits.size(); ++i) {
int num = digits[i] - '0';
if (num < 0 || num > 9) break;
const string& letters = v[num];
if (letters.empty()) continue;
vector tmp;
for (int j = 0 ; j < letters.size() ; ++j) {
for (int k = 0 ; k < result.size() ; ++k)
tmp.push_back(result[k] + letters[j]);
}
result.swap(tmp);
}
return result;