Hello Interview | Data Structures and Algorithms

Limited Time Offer:30% off Hello Interview Premium 🎉

30% off Hello Interview Premium 🎉

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Get Premium

Solution


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 = []
    
    def backtrack(combination, next_digits):
        if len(next_digits) == 0:
            combinations.append(combination)
            return
        
        for letter in digit_to_letters[next_digits[0]]:
            backtrack(combination + letter, next_digits[1:])
        return
    
    backtrack("", digits)
    return combinations

letter combinations of a phone number

0 / 40

Explanation

This problem uses backtracking to generate all possible combinations of letters that can be formed from a given string of digits.

It starts by creating a mapping of digits to letters, and then initializes an empty array combinations to store the generated combinations.

The solution uses a recursive function backtrack which takes in the current combination of letters combo, and the substring of next_digits that we are trying to construct a combination of digits from. Each function iterates over all the letters that the first digit in next_digits can represent. It'll then add the letter to the current combination and recursively call the backtrack function with the updated combination and the remaining digits in next_digits.


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 = []
    
    def backtrack(combination, next_digits):
        if len(next_digits) == 0:
            combinations.append(combination)
            return
        
        for letter in digit_to_letters[next_digits[0]]:
            backtrack(combination + letter, next_digits[1:])
        return
    
    backtrack("", digits)
    return combinations

letter combinations of a phone number

0 / 8

Whenever next_digits is empty, we know that we have formed a valid combination of letters and we can add it to the combinations array, and return from the function.


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 = []
    
    def backtrack(combination, next_digits):
        if len(next_digits) == 0:
            combinations.append(combination)
            return
        
        for letter in digit_to_letters[next_digits[0]]:
            backtrack(combination + letter, next_digits[1:])
        return
    
    backtrack("", digits)
    return combinations


    def backtrack(combination, next_digits):
        if len(next_digits) == 0:
            combinations.append(combination)
            return
        
        for letter in digit_to_letters[next_digits[0]]:
            backtrack(combination + letter, next_digits[1:])
        return


    def backtrack(combination, next_digits):
        if len(next_digits) == 0:
            combinations.append(combination)
            return
        
        for letter in digit_to_letters[next_digits[0]]:
            backtrack(combination + letter, next_digits[1:])
        return

letter = i

0 / 2

Exiting from a recursive call.

When the final call to backtrack returns, we have generated all possible combinations of letters and we can return the combinations array.


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 = []
    
    def backtrack(combination, next_digits):
        if len(next_digits) == 0:
            combinations.append(combination)
            return
        
        for letter in digit_to_letters[next_digits[0]]:
            backtrack(combination + letter, next_digits[1:])
        return
    
    backtrack("", digits)
    return combinations


    def backtrack(combination, next_digits):
        if len(next_digits) == 0:
            combinations.append(combination)
            return
        
        for letter in digit_to_letters[next_digits[0]]:
            backtrack(combination + letter, next_digits[1:])
        return

return from recursive call

0 / 2

Next: Overview

Mark as read

Your account is free and you can post anonymously if you choose.

Solution

Explanation

Questions

Learn

Links

Legal

Contact