Jobs

Interviews

Discussions

Letter Combinations of a Phone Number

Medium

Twitch

1 view

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

Twitch

1 view

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

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 should I return if the input string `digits` is empty?
Can the input string `digits` contain characters other than digits 2-9? If so, how should I handle them?
Are there any constraints on the length of the input string `digits`?
Is the order of the letter combinations in the output list important?
Can I assume that each digit in the input string `digits` will always map to a valid set of letters?

Brute Force Solution

Approach

We want to find all possible letter combinations for a given phone number's digits. The brute force approach explores every single combination until we've covered them all. It's like trying every single password until we guess the right one.

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

Look at the first digit of the phone number.
Consider each letter that the first digit maps to (for example, 2 maps to 'a', 'b', and 'c').
For each of those letters, look at the second digit and the letters it maps to.
Combine each letter from the first digit with each letter from the second digit.
Continue this process for each digit in the phone number, adding new letters to the existing combinations.
When you reach the end of the phone number, you have a complete letter combination.
Repeat the whole process, exploring every possibility for each digit, until you've generated all possible combinations.

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 []

    combinations = ['']

    for digit in digits:
        new_combinations = []

        # Iterate through existing combinations
        for combination in combinations:

            #  Iterate through letters of the current digit
            for letter in digit_to_letters[digit]:
                new_combinations.append(combination + letter)

        # This is to update to all possible combinations so far.
        combinations = new_combinations

    return combinations

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(4^n) – Let n be the length of the input digit string. Each digit maps to 3 or 4 letters. In the worst case, all digits map to 4 letters. The brute force approach explores every possible combination. For each digit, we potentially branch into 4 different possibilities. Thus, the number of possible combinations grows exponentially with the input size n. The total number of operations is approximately 4 * 4 * ... * 4 (n times) which is 4^n. Thus, the time complexity is O(4^n).

Space Complexity

O(3^N) – The space complexity is dominated by the list used to store the letter combinations. In the worst-case scenario, where each digit maps to 3 letters (digits 2-6, 8), and the input has N digits, we can have up to 3^N combinations. We also use a temporary string to store current combination during recursion, which takes O(N) space, and the recursion stack can go up to depth N, which takes O(N) space. Since 3^N dominates N, the auxiliary space is O(3^N).

Optimal Solution

Approach

The best way to find all letter combinations is to build them step-by-step, starting with the first digit and adding letters from each subsequent digit. This avoids generating useless combinations and focuses only on valid possibilities. It's like building a tree of choices, where each branch represents a possible letter.

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

First, create a connection between each number on the phone and its letters (like 2 maps to 'abc').
Start with an empty combination.
Look at the first digit. For each letter that corresponds to that digit, create a new combination by adding that letter to the empty combination.
Now, look at the second digit. For each combination you have, add each letter from the second digit to create even more combinations.
Keep doing this for each digit, taking all the combinations from the previous step and adding each letter from the next digit to them.
When you've used all the digits, you'll have a list of all the possible letter combinations. These are your solutions.

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'
    }

    result_combinations = ['']

    for digit in digits:
        new_combinations = []

        # Iterate over each existing combination
        for combination in result_combinations:

            # Create new combinations by adding letters.
            for letter in digit_to_letters[digit]:
                new_combinations.append(combination + letter)

        # Update combinations for next digit.
        result_combinations = new_combinations

    return result_combinations

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(4^n) – Let n be the number of digits in the input string. In the worst-case scenario, each digit maps to 4 letters (e.g., '7' or '9'). We are effectively building a tree where each level represents a digit and each node at that level branches out to the possible letters corresponding to that digit. The total number of combinations grows exponentially with the number of digits. Since each digit can potentially have up to 4 letters, the total number of combinations can reach 4^n. Thus, the time complexity is O(4^n).

Space Complexity

O(3^N) – The algorithm's space complexity is driven primarily by the storage of intermediate and final combinations. As described in the explanation, we build combinations step-by-step, where each digit can map to up to 3 or 4 letters (we'll consider the worst case where all digits map to 3 letters for simplification). In the worst case, we generate all possible combinations, and the number of combinations can grow exponentially with the length of the input digit string. Therefore, if N is the length of the input digit string, the maximum number of combinations stored is 3^N. Hence the space complexity is O(3^N).

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty list as there are no digits to generate combinations from.
Input string contains characters other than digits 2-9	Ignore the invalid characters or throw an exception, depending on requirements; the provided solution implicitly ignores by lack of mapping.
Input string contains a single digit	Return a list containing all letters associated with that digit.
Input string with a large number of digits (e.g., >10)	Ensure the algorithm scales efficiently, potentially using an iterative approach to avoid stack overflow issues from recursion.
Input consists of the same digit repeated multiple times (e.g., '222')	The algorithm should correctly generate all combinations, including those with repeated letters.
Combination length exceeds available memory	This should be tested against large inputs, and memory usage optimized; a streaming approach might be necessary if generating all combinations is infeasible.
Digits '0' or '1' in input.	These digits have no letter mapping and should be ignored or cause an exception depending on problem constraints.
Input '7777' generates an exponential number of combinations due to 4 letters mapped to '7'.	Be aware of exponential runtime and memory consumption, and consider imposing a limit on the input length.

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 should I return if the input string `digits` is empty?
Can the input string `digits` contain characters other than digits 2-9? If so, how should I handle them?
Are there any constraints on the length of the input string `digits`?
Is the order of the letter combinations in the output list important?
Can I assume that each digit in the input string `digits` will always map to a valid set of letters?

Brute Force Solution

Approach

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

Look at the first digit of the phone number.
Consider each letter that the first digit maps to (for example, 2 maps to 'a', 'b', and 'c').
For each of those letters, look at the second digit and the letters it maps to.
Combine each letter from the first digit with each letter from the second digit.
Continue this process for each digit in the phone number, adding new letters to the existing combinations.
When you reach the end of the phone number, you have a complete letter combination.
Repeat the whole process, exploring every possibility for each digit, until you've generated all possible combinations.

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 []

    combinations = ['']

    for digit in digits:
        new_combinations = []

        # Iterate through existing combinations
        for combination in combinations:

            #  Iterate through letters of the current digit
            for letter in digit_to_letters[digit]:
                new_combinations.append(combination + letter)

        # This is to update to all possible combinations so far.
        combinations = new_combinations

    return combinations

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, create a connection between each number on the phone and its letters (like 2 maps to 'abc').
Start with an empty combination.
Look at the first digit. For each letter that corresponds to that digit, create a new combination by adding that letter to the empty combination.
Now, look at the second digit. For each combination you have, add each letter from the second digit to create even more combinations.
Keep doing this for each digit, taking all the combinations from the previous step and adding each letter from the next digit to them.
When you've used all the digits, you'll have a list of all the possible letter combinations. These are your solutions.

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'
    }

    result_combinations = ['']

    for digit in digits:
        new_combinations = []

        # Iterate over each existing combination
        for combination in result_combinations:

            # Create new combinations by adding letters.
            for letter in digit_to_letters[digit]:
                new_combinations.append(combination + letter)

        # Update combinations for next digit.
        result_combinations = new_combinations

    return result_combinations

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty list as there are no digits to generate combinations from.
Input string contains characters other than digits 2-9	Ignore the invalid characters or throw an exception, depending on requirements; the provided solution implicitly ignores by lack of mapping.
Input string contains a single digit	Return a list containing all letters associated with that digit.
Input string with a large number of digits (e.g., >10)	Ensure the algorithm scales efficiently, potentially using an iterative approach to avoid stack overflow issues from recursion.
Input consists of the same digit repeated multiple times (e.g., '222')	The algorithm should correctly generate all combinations, including those with repeated letters.
Combination length exceeds available memory	This should be tested against large inputs, and memory usage optimized; a streaming approach might be necessary if generating all combinations is infeasible.
Digits '0' or '1' in input.	These digits have no letter mapping and should be ignored or cause an exception depending on problem constraints.
Input '7777' generates an exponential number of combinations due to 4 letters mapped to '7'.	Be aware of exponential runtime and memory consumption, and consider imposing a limit on the input length.