Letter Combinations of a Phone Number

Introduction

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

Solutions

1. Using Back-tracking(stack)

This solution uses a backtracking approach to generate all possible letter combinations for a given string of digits. We recursively build combinations by exploring all possible characters for each digit and combining them with the results of subsequent digits.

main.py

def letter_combinations_of_a_phone_number(digits: str) -> List[str]:
    mapping = {
        '2': 'abc',
        '3': 'def',
        '4': 'ghi',
        '5': 'jkl',
        '6': 'mno',
        '7': 'pqrs',
        '8': 'tuv',
        '9': 'wxyz',
    }

    def dfs(digits: str):
        if len(digits) == 0:
            return []
        if len(digits) == 1:
            return list(mapping[digits])
        return [
            char + a
            for a in dfs(digits[1:])
            for char in mapping[digits[0]]
        ]

    return dfs(digits)

2. Using BFS

Even though we haven't covered the BFS yet, this approach is more intuitive and easy to follow the flow.

main.py

def letter_combinations_of_a_phone_number(digits: str) -> List[str]:
    if not digits:
        return []
    
    mapping = {
        '2': 'abc',
        '3': 'def',
        '4': 'ghi',
        '5': 'jkl',
        '6': 'mno',
        '7': 'pqrs',
        '8': 'tuv',
        '9': 'wxyz',
    }
    
    combinations = ['']
    
    for digit in digits:
        letters = mapping[digit]
        new_combinations = []
        for combination in combinations:
            for letter in letters:
                new_combinations.append(combination + letter)
        combinations = new_combinations
    
    return combinations

Introduction

Solutions

1. Using Back-tracking(stack)

2. Using BFS

References