Phone Keypad Letter Combinations

1. Step 1: Initialize Solution.letterCombinations

   Replace the empty starter with the first real state owned by Solution.letterCombinations. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.

2. Step 2: Assemble the primary transition

   Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.

3. Step 3: Pass the Two Digits case

   Complete the readable core algorithm for one representative Interview case. Model one recursive decision per input digit and emit only complete paths.

4. Step 4: Harden the Four Letter Key boundary

   Repair the reviewed boundary and pass the complete submission contract. At depth i the path contains exactly one mapped letter for each of the first i digits; branching over every mapping and emitting at full depth produces every valid combination exactly once.

• An empty digit string has no combinations, rather than one empty-string combination.
• recursion and backtracking

• LeetCode 17 — Letter Combinations of a Phone Number
• Hello Interview — Backtracking Overview

• Complete One Backtracking Frame(opens in a new tab)

  Complete One Backtracking Frame isolates before expanding each choice, path equals the original caller-owned prefix; every emitted candidate contains exactly one additional element. That focused state discipline is required when implementing letter combinations phone as a complete Interview Problem.

Backtrack by digit index, append each mapped letter, then remove it before trying the next letter.

Why it works: At depth i the path contains exactly one mapped letter for each of the first i digits; branching over every mapping and emitting at full depth produces every valid combination exactly once.

class Solution:
    def letterCombinations(self, digits):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        if not digits:
            return []
        mapping = {
            '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
            '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz',
        }
        result = []
        path = []
        def backtrack(index):
            if index == len(digits):
                result.append(''.join(path))
                return
            for letter in mapping[digits[index]]:
                path.append(letter)
                backtrack(index + 1)
                path.pop()
        backtrack(0)
        return result

• Generate Balanced Parentheses(opens in a new tab)