## Similar Problems

Similar Problems not available

# Letter Combinations Of A Phone Number - Leetcode Solution

LeetCode: Letter Combinations Of A Phone Number Leetcode Solution

Difficulty: Medium

Topics: string hash-table backtracking

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

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:

- Create a hash-map to store mappings
- Define a helper function that takes in two parameters:
- A string 'output' to store all possible combinations
- An integer 'index' representing the current index to process in digits

- If index == length of digits, append the output to the result and return
- Find all characters corresponding to 'digits[index]' in the hash-map
- Loop through the characters and recursively call the helper function with:
- 'output' appended with the current character being processed
- 'index+1' as the new index to process in digits

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

## Letter Combinations Of A Phone Number Solution Code

`1`