Generating Phone Keypad Combinations in Python

Rate this post

πŸ’‘ Problem Formulation: In this article, we explore how to generate all possible strings that can be typed using a traditional phone keypad. Each number (2-9) on a phone keypad corresponds to a set of letters. For example, 2 corresponds to “abc”. Given a sequence of number inputs like ’23’, we aim to find all possible letter combinations like [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

Method 1: Recursive Function Approach

This method implements a helper function that follows the recursive approach. It takes an index and a partial combination, then for the number at the current index, it adds the corresponding letters and recursively calls itself for the next index, building up the combinations as it goes.

Here’s an example:

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

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

    def backtrack(index, path):
        if len(path) == len(digits):
            combinations.append(''.join(path))
            return
        possible_letters = phone_map[digits[index]]
        for letter in possible_letters:
            path.append(letter)
            backtrack(index + 1, path)
            path.pop()

    combinations = []
    backtrack(0, [])
    return combinations

print(letter_combinations('23'))

Output:

['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']

This snippet first checks if the input string digits is empty and returns an empty list if so. Otherwise, it initializes a dictionary mapping digits to their corresponding letters and a recursive function called backtrack that builds the combinations by exploring all possible paths through the keypad letter mappings. The final list of combinations is then returned.

Method 2: Iterative Looping

The iterative method iterates over the input digits, updating a temporary list with all possible combinations from the previous step with each new digit considered.

Here’s an example:

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

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

    combinations = ['']
    for digit in digits:
        next_combinations = []
        for old_combination in combinations:
            for letter in phone_map[digit]:
                next_combinations.append(old_combination + letter)
        combinations = next_combinations

    return combinations

print(iterative_letter_combinations('23'))

Output:

['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']

The given code snippet uses an iterative approach to build up the list of letter combinations possible from the digit string. It starts with an initial list containing an empty string and, for each digit, creates a new list by combining every existing combination with each letter corresponding to the current digit.

Method 3: Using itertools.product()

This method leverages Python’s itertools.product() to create a Cartesian product of the possible characters for each digit, thus generating all possible combinations effortlessly.

Here’s an example:

import itertools

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

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

    char_tuples = [phone_map[digit] for digit in digits]
    combinations = [''.join(comb) for comb in itertools.product(*char_tuples)]

    return combinations

print(product_letter_combinations('23'))

Output:

['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']

In this approach, itertools.product() is utilized to create a product of the characters mapped to each digit in the input. The product() function takes care of generating all combinations, which are then joined together into strings to form the final list of letter combinations.

Method 4: Using a Queue

This method involves simulating the combination generation process using a queue. It starts by enqueuing an empty string and in each iteration, dequeues existing items, appending the next possible set of letters one by one until all combinations are formed.

Here’s an example:

from collections import deque

def queue_letter_combinations(digits) -> list:
    if not digits:
        return []

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

    q = deque([''])
    
    for digit in digits:
        for _ in range(len(q)):
            previous = q.popleft()
            for letter in phone_map[digit]:
                q.append(previous + letter)
                
    return list(q)

print(queue_letter_combinations('23'))

Output:

['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']

The code maintains a queue that is used to build the combinations incrementally. For each digit, it appends every possible corresponding letter to previous strings and re-inserts them back into the queue. This happens repeatedly until all combinations are created.

Bonus One-Liner Method 5: List Comprehension Approach

This method utilizes a concise one-liner using list comprehension to achieve the same result, combining simplicity and effectiveness.

Here’s an example:

from functools import reduce

def one_liner_letter_combinations(digits):
    phone_map = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
    }
    return reduce(lambda acc, digit: [x + y for x in acc for y in phone_map[digit]], digits, [''])

print(one_liner_letter_combinations('23'))

Output:

['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']

The one-liner uses reduce() to apply a function that accumulates combinations by adding each possible letter to every existing string in the accumulator. The result is a concise yet powerful single line that produces the required list of combinations.

Summary/Discussion

  • Method 1: Recursive Function Approach. Simple and straightforward recursive solution. Strengths: clear logical flow. Weaknesses: can be difficult to understand for beginners, not as efficient for large digit strings.
  • Method 2: Iterative Looping. Eliminates the need for recursive calls. Strengths: more intuitive for those familiar with iterative solutions. Weaknesses: requires additional space to store intermediate results.
  • Method 3: Using itertools.product(). Leverages inbuilt Python library functions to reduce code needed. Strengths: very succinct and easy to read. Weaknesses: less control over the internal workings and may be slightly less efficient due to the generation of tuples.
  • Method 4: Using a Queue. Simulates a breadth-first generation of combinations. Strengths: efficient in both time and space complexity. Weaknesses: slightly less intuitive than other methods.
  • Bonus Method 5: List Comprehension Approach. Provides a one-liner solution using list comprehension and reduce(). Strengths: extremely concise. Weaknesses: potentially less readable for complex logic or long input strings.