Letter Combinations of a Phone Number — Python Backtracking

Letter Combinations of a Phone Number — Python Backtracking

Read time: ~6 min • Tags: Python, Backtracking, Algorithms

Problem Overview

Given a string containing digits from 2 to 9, return all possible letter combinations that the number could represent, using the classic telephone mapping:

2: abc
3: def
4: ghi
5: jkl
6: mno
7: pqrs
8: tuv
9: wxyz

Example: Input: "23" → Output:

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

Approach — Backtracking (recommended)

Backtracking constructs combinations by choosing one letter for each digit, recursing to the next digit, then undoing the choice (classic DFS of the combinatorial tree).

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

    mapping = {
        "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
        "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"
    }
    res = []
    path = []

    def backtrack(index: int):
        if index == len(digits):
            res.append(''.join(path))
            return
        letters = mapping[digits[index]]
        for ch in letters:
            path.append(ch)
            backtrack(index + 1)
            path.pop()

    backtrack(0)
    return res

# Example
print(letter_combinations_backtrack('23'))

Complexity: For input length n, if average letters per digit = k (≈3–4), time and space are O(k^n) — which is expected for enumerating all combinations.

Alternative — Iterative (BFS style)

You can build combinations iteratively using a queue/list. This is conceptually BFS over the digit positions.

from collections import deque

def letter_combinations_iterative(digits: str) -> list:
    if not digits:
        return []
    mapping = {
        "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
        "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"
    }
    queue = ['']
    for d in digits:
        letters = mapping[d]
        new_queue = []
        for prefix in queue:
            for ch in letters:
                new_queue.append(prefix + ch)
        queue = new_queue
    return queue

print(letter_combinations_iterative('23'))

Edge Cases & Notes

• Empty input should return an empty list (not [""]).
• Digits 0 and 1 have no mappings and should be considered invalid unless you define a custom mapping.
• Use the backtracking method in interviews — it's concise and demonstrates recursion understanding.

Developer Task (Hands-on)

Implement and submit these small exercises to practice:

1. Write letter_combinations_backtrack and letter_combinations_iterative and compare runtime for increasing digit lengths (2–6 digits). Record results.
2. Extend the function to accept digits containing 0 and 1 where:
• 0 maps to " " (space), 1 maps to "*" — or implement skipping them.
3. Harder: Given a dictionary of valid words, return only combinations that are valid English words (prune using prefix checking/trie).

Challenge: For the word-checker task, build a trie of valid words and prune branches early when no word starts with the current prefix — this reduces search drastically.

FAQ

Q: Why use backtracking instead of nested loops?

A: Nested loops require knowing the input size at code time. Backtracking scales to any length and keeps code readable.

Q: Will this solution work for very long digit strings?

A: No — the number of combinations grows exponentially. For long strings, you must limit output or search only for matching dictionary entries.

Q: How to generate combinations in lexicographic order?

A: If your mapping letters are in lexicographic order (e.g., 'abc'), the backtracking solution already produces lexicographic output.

📱 Python GUI Project: Letter Combinations of a Phone Number

Want to take your Python skills further? Let's build a modern GUI app that generates all possible letter combinations from phone digits. This project demonstrates backtracking in action with an interactive interface.

import customtkinter as ctk
from tkinter import messagebox

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

def backtrack(digits, index, path, res):
    if index == len(digits):
        res.append(''.join(path))
        return
    for ch in mapping[digits[index]]:
        path.append(ch)
        backtrack(digits, index + 1, path, res)
        path.pop()

def generate_combinations():
    digits = entry.get().strip()
    if not digits or any(d not in mapping for d in digits):
        messagebox.showwarning("Invalid Input", "Enter digits 2-9 only")
        return
    res = []
    backtrack(digits, 0, [], res)
    result_label.configure(text=', '.join(res))

# GUI Setup
ctk.set_appearance_mode("dark")
ctk.set_default_color_theme("blue")

app = ctk.CTk()
app.geometry("550x450")
app.title("📱 Letter Combinations Checker")

title = ctk.CTkLabel(app, text="📱 Letter Combinations of Phone Number", font=("Segoe UI", 20, "bold"))
title.pack(pady=20)

entry = ctk.CTkEntry(app, width=220, height=40, font=("Segoe UI", 16), placeholder_text="Enter digits 2-9")
entry.pack(pady=10)

btn = ctk.CTkButton(app, text="Generate Combinations", font=("Segoe UI", 16), command=generate_combinations)
btn.pack(pady=12)

result_label = ctk.CTkLabel(app, text="", font=("Segoe UI", 14), wraplength=500)
result_label.pack(pady=20)

footer = ctk.CTkLabel(app, text="Made with ❤️ in Python | CodingBihar", font=("Segoe UI", 12))
footer.pack(side="bottom", pady=10)

app.mainloop()

Result:

How it Works:

• The backtrack function recursively builds letter combinations for each digit.
• Once a complete combination is ready, it’s added to the results list.
• The GUI displays results interactively using CustomTkinter, with input validation for digits 2-9.
• Users can see all possible combinations instantly in a clean, modern interface.

How to Run:

1. Install CustomTkinter: pip install customtkinter
2. Save the code above as letter_combinations_gui.py
3. Run: python letter_combinations_gui.py
4. Enter digits 2-9 and click "Generate Combinations" to see all results!

Try It Yourself:

• Modify the app to filter only valid English words from a dictionary.
• Implement an iterative (queue-based) solution instead of recursion.
• Add a copy-to-clipboard button for generated combinations.
• Add a history panel to store the last 5 inputs.

Conclusion

Generating letter combinations is a classic combinatorics + string-building problem. Backtracking is the idiomatic solution and a great interview example to show recursion, pruning, and complexity awareness. Try the developer tasks and consider extending the post with a demo web UI (JS) or a trie-based word filter.

Featured image suggestion: a flat illustration showing a vintage phone keypad and letter tiles (size 1200×630). Social copy: “Learn backtracking in Python — generate letter combinations for phone digits. Code, tasks and interview tips.”

Internal links: Backtracking Patterns — A Practical Guide | Trie Data Structure in Python