Jobs

Interviews

Discussions

Letter Combinations of a Phone Number

Medium

Apple

4 views

Topics:

StringsRecursion

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

Letter Combinations of a Phone Number

Medium

Apple

4 views

Topics:

StringsRecursion

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

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What happens if the input string `digits` is empty or null?
Can the input `digits` contain characters other than the digits 2-9?
Is the order of the letter combinations in the output important?
Are the mappings from digits to letters fixed as per a standard phone keypad, or should I expect a different mapping?
Can I assume that the input `digits` will not be excessively long, such as longer than 10 digits?

Brute Force Solution

Approach

The goal is to find all possible letter combinations that can be formed from a given string of digits, where each digit corresponds to certain letters on a phone keypad. The brute force way is to explore every possible combination of letters by trying each one out.

Here's how the algorithm would work step-by-step:

For the first digit, consider each letter it maps to.
For each of those letters, consider each letter that the second digit maps to, creating all possible two-letter combinations.
Continue this process for each subsequent digit, adding the letters it maps to, to the existing combinations.
Repeat until you have explored all digits, generating every possible combination of letters.
The result is a collection of all possible letter strings that can be made from the given digits.

Code Implementation

def letter_combinations_brute_force(digits):    digit_to_letters = {
        '2': 'abc',
        '3': 'def',
        '4': 'ghi',
        '5': 'jkl',
        '6': 'mno',
        '7': 'pqrs',
        '8': 'tuv',
        '9': 'wxyz'
    }

    if not digits:
        return []

    letter_combinations = ['']

    for digit in digits:
        # Need to store the newly created combinations
        new_combinations = []

        for combination in letter_combinations:
            for letter in digit_to_letters[digit]:
                # Append letter to form new combination
                new_combinations.append(combination + letter)

        # Update existing combinations with new ones
        letter_combinations = new_combinations

    return letter_combinations

Big(O) Analysis

Time Complexity

O(4^n) – The time complexity is driven by the number of possible letter combinations. Each digit (except 1 and 0) maps to 3 or 4 letters. In the worst-case scenario where every digit maps to 4 letters, and given an input of n digits, the algorithm explores 4 options for the first digit, then 4 for the second, and so on. This results in exploring 4 * 4 * ... * 4 (n times), leading to 4^n possible combinations. Therefore, the time complexity is O(4^n).

Space Complexity

O(3^N) – The space complexity is primarily determined by the size of the output list containing all possible letter combinations. In the worst-case scenario, where each digit maps to 3 letters (e.g., '2', '3', '4', '5', '6', '8'), and given an input string of length N, the number of combinations grows exponentially as 3^N. Additionally, the recursion stack used implicitly by the recursive calls can reach a depth of N in the worst case, but its space usage O(N) is dominated by the space required for the final combinations. Therefore, the overall space complexity is O(3^N).

Optimal Solution

Approach

The optimal way to generate letter combinations from a phone number involves building combinations step-by-step. Instead of creating every combination at once, we'll grow the possible combinations with each new digit. This avoids unnecessary calculations and makes the solution much faster.

Here's how the algorithm would work step-by-step:

Think of each number on the phone as having its own set of letters. The first number's letters are your starting point.
Take each letter from your starting point and combine it with all the letters from the second number. Now you have more combinations.
Repeat this process for each subsequent number. Take each of your current combinations and add all the letters from the next number to it.
Continue until you've processed all the numbers. The resulting combinations are all the possible letter combinations for the phone number.

Code Implementation

def letterCombinations(digits):
    if not digits:
        return []

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

    combinations = ['']

    for digit in digits:
        # Expand combinations based on letters of current digit
        new_combinations = []

        for combination in combinations:
            for letter in digit_to_letters[digit]:
                new_combinations.append(combination + letter)

        combinations = new_combinations

    return combinations

Big(O) Analysis

Time Complexity

O(4^n) – The time complexity is driven by the number of possible combinations. If we consider the worst-case scenario where each digit maps to 4 letters (e.g., '7' maps to 'PQRS'), and the input 'digits' string has a length of n, then the number of combinations grows exponentially. For each digit, we effectively multiply the existing combinations by at most 4. Thus, in the worst case, we end up with approximately 4^n combinations, where n is the length of the input digits string. Therefore, the time complexity to generate these combinations is O(4^n).

Space Complexity

O(3^N) – The algorithm's space complexity is primarily determined by the size of the combinations generated at each step. In the worst case, each digit can map to 3 or 4 letters. Since we are building upon the existing combinations with each new digit, we store the intermediate combinations in a temporary data structure. If N is the number of digits in the input phone number, and assuming each digit maps to an average of 3 letters, the number of combinations can grow up to 3^N. Thus, the space required to store these combinations is O(3^N).

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty list since no combinations can be formed.
Input string contains characters other than digits 2-9	Ignore invalid characters or throw an IllegalArgumentException based on problem constraints.
Input string with a single digit	Return the letters corresponding to that digit as individual strings in a list.
Input string with all identical digits (e.g., '222')	The algorithm should correctly generate all combinations of the same letters.
Long input string (e.g., 8+ digits)	The solution scales exponentially with the length of the input, so time complexity must be considered and stated.
Input string resulting in a very large number of combinations (close to memory limits)	Ensure the algorithm doesn't exceed memory limits, potentially leading to an OutOfMemoryError.
Digit '1' is present in the input	Digit '1' should be skipped since it does not map to any letters.
Digit '0' is present in the input	Digit '0' should be skipped since it does not map to any letters.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What happens if the input string `digits` is empty or null?
Can the input `digits` contain characters other than the digits 2-9?
Is the order of the letter combinations in the output important?
Are the mappings from digits to letters fixed as per a standard phone keypad, or should I expect a different mapping?
Can I assume that the input `digits` will not be excessively long, such as longer than 10 digits?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

For the first digit, consider each letter it maps to.
For each of those letters, consider each letter that the second digit maps to, creating all possible two-letter combinations.
Continue this process for each subsequent digit, adding the letters it maps to, to the existing combinations.
Repeat until you have explored all digits, generating every possible combination of letters.
The result is a collection of all possible letter strings that can be made from the given digits.

Code Implementation

def letter_combinations_brute_force(digits):    digit_to_letters = {
        '2': 'abc',
        '3': 'def',
        '4': 'ghi',
        '5': 'jkl',
        '6': 'mno',
        '7': 'pqrs',
        '8': 'tuv',
        '9': 'wxyz'
    }

    if not digits:
        return []

    letter_combinations = ['']

    for digit in digits:
        # Need to store the newly created combinations
        new_combinations = []

        for combination in letter_combinations:
            for letter in digit_to_letters[digit]:
                # Append letter to form new combination
                new_combinations.append(combination + letter)

        # Update existing combinations with new ones
        letter_combinations = new_combinations

    return letter_combinations

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Think of each number on the phone as having its own set of letters. The first number's letters are your starting point.
Take each letter from your starting point and combine it with all the letters from the second number. Now you have more combinations.
Repeat this process for each subsequent number. Take each of your current combinations and add all the letters from the next number to it.
Continue until you've processed all the numbers. The resulting combinations are all the possible letter combinations for the phone number.

Code Implementation

def letterCombinations(digits):
    if not digits:
        return []

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

    combinations = ['']

    for digit in digits:
        # Expand combinations based on letters of current digit
        new_combinations = []

        for combination in combinations:
            for letter in digit_to_letters[digit]:
                new_combinations.append(combination + letter)

        combinations = new_combinations

    return combinations

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty list since no combinations can be formed.
Input string contains characters other than digits 2-9	Ignore invalid characters or throw an IllegalArgumentException based on problem constraints.
Input string with a single digit	Return the letters corresponding to that digit as individual strings in a list.
Input string with all identical digits (e.g., '222')	The algorithm should correctly generate all combinations of the same letters.
Long input string (e.g., 8+ digits)	The solution scales exponentially with the length of the input, so time complexity must be considered and stated.
Input string resulting in a very large number of combinations (close to memory limits)	Ensure the algorithm doesn't exceed memory limits, potentially leading to an OutOfMemoryError.
Digit '1' is present in the input	Digit '1' should be skipped since it does not map to any letters.
Digit '0' is present in the input	Digit '0' should be skipped since it does not map to any letters.