Letter Combinations Of A Phone Number - Leetcode Solution

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:

1. Create a hash-map to store mappings
2. 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
3. If index == length of digits, append the output to the result and return
4. Find all characters corresponding to 'digits[index]' in the hash-map
5. 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
6. 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.

1