Letter Combinations of Phone Number

▶

Steps

setup

Initialize queue with empty string

The algorithm starts by initializing a queue containing an empty string to represent the starting point for building combinations.

💡 Starting with an empty string allows the algorithm to append letters for each digit step-by-step.

Line:

queue = deque([''])

💡 The queue holds all partial combinations; initially, it contains only the empty string.

fill_row

Process first digit '2' - get letters 'abc'

The algorithm retrieves the letters mapped to digit '2', which are 'a', 'b', and 'c'.

💡 Mapping digits to letters is essential to know which letters to append next.

Line:

letters = digit_map[digit]  # digit = '2'

💡 Digit '2' corresponds to letters 'abc', which will be appended to existing partial strings.

fill_cells

Expand queue for digit '2' - dequeue '' and enqueue 'a', 'b', 'c'

The algorithm dequeues the empty string and appends each letter from 'abc', enqueuing 'a', 'b', and 'c'.

💡 This step shows how partial strings grow by one letter for the current digit.

Line:

prev = queue.popleft()
for char in letters:
    queue.append(prev + char)

💡 The queue now contains all partial combinations after processing the first digit.

fill_row

Process second digit '3' - get letters 'def'

The algorithm retrieves the letters mapped to digit '3', which are 'd', 'e', and 'f'.

💡 Knowing the letters for the current digit is necessary to expand existing partial strings.

Line:

letters = digit_map[digit]  # digit = '3'

💡 Digit '3' corresponds to letters 'def', which will be appended to each string in the queue.

fill_cells

Expand queue for digit '3' - dequeue 'a' and enqueue 'ad', 'ae', 'af'

The algorithm dequeues 'a' and appends each letter from 'def', enqueuing 'ad', 'ae', and 'af'.

💡 This step shows how each partial string is expanded by one letter for the current digit.

Line:

prev = queue.popleft()
for char in letters:
    queue.append(prev + char)

💡 Partial string 'a' expands into three new strings, increasing the queue size.

fill_cells

Expand queue for digit '3' - dequeue 'b' and enqueue 'bd', 'be', 'bf'

The algorithm dequeues 'b' and appends each letter from 'def', enqueuing 'bd', 'be', and 'bf'.

💡 Each partial string is expanded fully before moving to the next, ensuring all combinations are generated.

Line:

prev = queue.popleft()
for char in letters:
    queue.append(prev + char)

💡 Partial string 'b' expands into three new strings, continuing the queue growth.

fill_cells

Expand queue for digit '3' - dequeue 'c' and enqueue 'cd', 'ce', 'cf'

The algorithm dequeues 'c' and appends each letter from 'def', enqueuing 'cd', 'ce', and 'cf'.

💡 This completes the expansion for all partial strings from the first digit.

Line:

prev = queue.popleft()
for char in letters:
    queue.append(prev + char)

💡 Partial string 'c' expands into three new strings, completing the queue expansion.

reconstruct

All digits processed - queue contains all combinations

After processing all digits, the queue holds all complete letter combinations but has not yet been converted to a list.

💡 The queue now fully represents the solution space before final conversion.

Line:

queue  # contains all combinations

💡 The queue is the final data structure holding all valid combinations before returning.

reconstruct

Convert queue to list for final output

The algorithm converts the queue containing all letter combinations into a list to prepare for returning the result.

💡 Converting the queue to a list formats the output as expected by the caller.

Line:

return list(queue)

💡 This conversion finalizes the data structure for output.

reconstruct

Return final list of letter combinations

The algorithm returns the list of all letter combinations generated from the input digits.

💡 This final step outputs the complete set of combinations as the solution.

Line:

return list(queue)

💡 The final answer contains all possible letter combinations for digits '2' and '3'.

from collections import deque

def letterCombinations(digits):
    if not digits:
        return []  # STEP 1: Handle empty input
    digit_map = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
                 '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
    queue = deque([''])  # STEP 2: Initialize queue with empty string
    for digit in digits:  # STEP 3: Iterate over each digit
        letters = digit_map[digit]  # STEP 4: Get letters for current digit
        for _ in range(len(queue)):  # STEP 5: Expand all partial strings
            prev = queue.popleft()  # STEP 6: Dequeue one partial string
            for char in letters:  # STEP 7: Append each letter
                queue.append(prev + char)  # STEP 8: Enqueue new string
    return list(queue)  # STEP 9: Return all combinations as list

📊

Letter Combinations of Phone Number - Watch the Algorithm Execute, Step by Step

Watching each step of the queue expansion reveals how the algorithm systematically explores all letter combinations without recursion, making the backtracking concept clearer.

enteringdigits="23"

Call Path (current → root)

letterCombinations('23')

Remaining

process digit '2'process digit '3'

Partial: []

choosingdigits="23"

Call Path (current → root)

letterCombinations('23')

Tried

process digit '2'

Remaining

process digit '3'

Partial: []

choosingdigits="23"

Call Path (current → root)

letterCombinations('23')

Tried

process digit '2'

Remaining

process digit '3'

Partial: [a, b, c]

choosingdigits="23"

Call Path (current → root)

letterCombinations('23')

Tried

process digit '2'process digit '3'

Partial: [a, b, c]

choosingdigits="23"

Call Path (current → root)

letterCombinations('23')

Tried

process digit '2'process digit '3'

Partial: [b, c, ad, ae, af]

choosingdigits="23"

Call Path (current → root)

letterCombinations('23')

Tried

process digit '2'process digit '3'

Partial: [c, ad, ae, af, bd, be, bf]

choosingdigits="23"

Call Path (current → root)

letterCombinations('23')

Tried

process digit '2'process digit '3'

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

backtrackingdigits="23"

Call Path (current → root)

letterCombinations('23')

Tried

process digit '2'process digit '3'

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

Found 9: [ce] [cf]

backtrackingdigits="23"

Call Path (current → root)

letterCombinations('23')

Tried

process digit '2'process digit '3'

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

Found 9: [ce] [cf]

backtrackingdigits="23"

Call Path (current → root)

letterCombinations('23')

Tried

process digit '2'process digit '3'

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

Found 9: [ce] [cf]

Key Takeaways

✓ The queue-based iterative approach systematically builds all letter combinations by expanding partial strings one digit at a time.

This insight is hard to see from code alone because the queue operations and expansions happen implicitly; visualization makes the process explicit.

✓ Each digit's letters are appended to all existing partial strings before moving to the next digit, ensuring complete coverage of combinations.

Seeing the queue grow step-by-step clarifies how the algorithm avoids recursion but still explores all paths.

✓ The algorithm never prunes any paths because all letter combinations are valid, demonstrating a full exhaustive search.

Understanding that no pruning occurs helps learners distinguish this from backtracking algorithms that prune invalid paths.

Practice

1. What is the time complexity of the optimal backtracking solution for the Expression Add Operators problem, where n is the length of the input string? Assume the solution tries all operator insertions and substring splits with pruning and efficient string building.

medium

A. O(4^n) because at each position there are up to 4 choices (3 operators + no operator split)

B. O(n * 3^n) because each digit can be combined with 3 operators and substring splits

C. O(2^n) since only two operators are considered at each step

D. O(n^3) due to substring parsing and operator insertions

Solution

1. Step 1: Identify branching factor per digit

   At each digit, we can insert one of 3 operators (+, -, *) or choose to extend the current operand (no operator), but the main branching factor is 3 operators per split, and substring splits add a factor of n.

2. Step 2: Calculate total complexity

   The total complexity is roughly O(n * 3^n) because for each of the n positions, there are up to 3 operator choices, and substring splits add an n factor.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Exponential branching with 3 operators and substring splits [OK]

Hint: 3 operators per digit and substring splits lead to O(n * 3^n) complexity [OK]

Common Mistakes:

• Confusing substring parsing cost as cubic
• Assuming only 2 operators reduce complexity
• Miscounting branching factor as 4

2. Examine the following buggy code snippet for Expression Add Operators. Which line contains the subtle bug that causes incorrect results on inputs with leading zeros?

def addOperators(num: str, target: int) -> List[str]:
    res = []
    path = []
    def backtrack(index: int, evaluated: int, last_operand: int):
        if index == len(num):
            if evaluated == target:
                res.append(''.join(path))
            return
        for i in range(index, len(num)):
            # Bug: missing leading zero check
            curr_str = num[index:i+1]
            curr = int(curr_str)
            length_before = len(path)
            if index == 0:
                path.append(curr_str)
                backtrack(i+1, curr, curr)
                path[length_before:] = []
            else:
                path.append('+'); path.append(curr_str)
                backtrack(i+1, evaluated + curr, curr)
                path[length_before:] = []
    backtrack(0, 0, 0)
    return res

medium

A. Line with 'if i != index and num[index] == '0':' missing here

B. Line with 'curr_str = num[index:i+1]' (substring extraction)

C. Line with 'path[length_before:] = []' (backtracking cleanup)

D. Line with 'path.append('+'); path.append(curr_str)' (operator insertion)

Solution

1. Step 1: Identify handling of leading zeros

   The code lacks the check 'if i != index and num[index] == '0': break' which prevents invalid operands like "05".

2. Step 2: Confirm bug location

   This missing check is critical and should be placed before parsing curr_str to avoid invalid expressions.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing leading zero check causes invalid operands [OK]

Hint: Leading zero check missing causes invalid operands [OK]

Common Mistakes:

• Confusing backtracking cleanup lines as bug
• Thinking substring extraction is buggy

3. Identify the bug in the following code snippet for getPermutation:

medium

A. Line 6: k is not converted to zero-based index before calculations.

B. Line 2: factorial array initialization is incorrect.

C. Line 10: The index calculation uses integer division incorrectly.

D. Line 12: numbers.pop(idx) should be numbers.remove(idx).

Solution

1. Step 1: Check k adjustment

   k must be decremented by 1 to convert to zero-based indexing before using factorial divisions.

2. Step 2: Understand impact of missing k -= 1

   Without this, idx calculation is off by one, leading to incorrect permutation output.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing k -= 1 causes wrong indexing and wrong permutation [OK]

Hint: Always convert k to zero-based before factorial indexing [OK]

Common Mistakes:

• Forgetting zero-based index adjustment
• Misusing pop vs remove
• Incorrect factorial initialization

4. Suppose you want to generate all valid parentheses sequences of length 2n, but now you can reuse parentheses pairs multiple times (i.e., sequences can contain repeated pairs). Which modification to the backtracking algorithm correctly handles this variant?

hard

A. Use memoization to store and reuse previously generated valid sequences to handle repeated pairs

B. Keep the original constraints but allow adding '(' or ')' even if counts exceed n, then filter duplicates after generation

C. Modify the algorithm to generate sequences of length 2n without constraints, then check validity and uniqueness

D. Remove the limit on open_count and close_count, allowing unlimited '(' and ')' additions

Solution

1. Step 1: Understand reuse requirement

   Reusing pairs means sequences can contain repeated valid substrings; naive pruning breaks this.

2. Step 2: Analyze modifications

   Removing limits or generating all sequences leads to invalid or duplicate sequences. Memoization allows reusing computed valid sequences efficiently.

3. Step 3: Choose correct approach

   Memoization stores and reuses valid subsequences, enabling correct generation with reuse.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Memoization handles reuse without generating invalid sequences [OK]

Hint: Memoization enables reuse without invalid sequences [OK]

Common Mistakes:

• Removing constraints causes invalid sequences
• Filtering duplicates after generation is inefficient

5. Suppose the problem is modified so that the same letter cell can be reused multiple times in forming a single word. Which modification to the backtracking with Trie approach correctly handles this change without causing infinite loops?

hard

A. Use a memoization cache keyed by (row, col, Trie node) to avoid infinite loops.

B. Keep visited marking but reset it after each recursive call to allow reuse.

C. Remove visited marking and add a recursion depth limit equal to word length.

D. Remove visited marking and rely on Trie pruning only.

Solution

1. Step 1: Understand reuse implications

   Allowing reuse of cells means cycles can occur, causing infinite recursion without additional safeguards.

2. Step 2: Identify correct prevention method

   Memoization keyed by (row, col, Trie node) prevents revisiting the same state repeatedly, breaking cycles and infinite loops.

3. Step 3: Evaluate other options

   Removing visited marking alone causes infinite loops; depth limit is arbitrary and may miss valid paths; resetting visited marking still forbids reuse within one path.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Memoization ensures correctness with cell reuse allowed [OK]

Hint: Memoization avoids infinite loops when cells can be reused [OK]

Common Mistakes:

• Removing visited marking without cycle detection causes infinite loops.