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 algorithm that generates unique permutations of an array with duplicates by sorting and skipping duplicates during recursion?

medium

A. O(n! * log n) due to sorting and binary search for duplicates

B. O(n! * n^2) because each permutation requires copying the array and checking duplicates

C. O(n^n) because the recursion explores all possible swaps without pruning

D. O(n! * n) because pruning duplicates early reduces redundant branches but each permutation still requires O(n) copying

Solution

1. Step 1: Identify complexity of outer and inner loops

   Backtracking explores permutations, which is O(n!). Each permutation requires copying O(n) elements to result.

2. Step 2: Check if pruning duplicates reduces complexity

   Pruning duplicates early avoids redundant branches, so complexity is O(n! * n), not worse. Sorting is O(n log n) but done once.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Pruning reduces branches but copying each permutation costs O(n) [OK]

Hint: Pruning duplicates reduces branches but copying costs O(n) per permutation [OK]

Common Mistakes:

• Confusing pruning effect or ignoring copy cost

2. The following code attempts to generate all permutations of a list using Heap's algorithm but contains a subtle bug:

def permute(nums):
    res = [nums[:]]
    c = [0] * len(nums)
    i = 0
    while i < len(nums):
        if c[i] < i:
            if i % 2 == 0:
                nums[0], nums[i] = nums[i], nums[0]
            else:
                nums[c[i]], nums[i] = nums[i], nums[c[i]]
            res.append(nums)
            c[i] += 1
            i = 0
        else:
            c[i] = 0
            i += 1
    return res

What is the bug in this code?

medium

A. The used array c is not reset properly, causing infinite loop

B. Appending nums directly without copying causes all entries in res to reference the same list

C. Swapping nums[0] and nums[i] when i is even is incorrect logic

D. The initial res list should be empty, not contain nums[:] at start

Solution

1. Step 1: Identify how results are stored

   The code appends nums directly to res without copying.

2. Step 2: Understand consequences of appending references

   Since nums is mutated in-place, all entries in res point to the same list, resulting in duplicates of the final permutation.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Appending a copy nums[:] fixes the bug [OK]

Hint: Always append a copy of mutable lists to results [OK]

Common Mistakes:

• Forgetting to copy before appending results in duplicate references

3. Consider the following buggy code snippet for restoring IP addresses. Which line contains the subtle bug that causes invalid IP addresses to be included?

def restore_ip_addresses(s: str) -> List[str]:
    res = []
    stack = [(0, [])]
    while stack:
        start, path = stack.pop()
        if len(path) == 4:
            if start == len(s):
                res.append(".".join(path))
            continue
        remaining_segments = 4 - len(path)
        remaining_chars = len(s) - start
        if remaining_chars < remaining_segments or remaining_chars > 3 * remaining_segments:
            continue
        for length in range(1, 4):
            if start + length > len(s):
                break
            segment = s[start:start+length]
            # Bug: Missing check for leading zeros
            if length == 3 and int(segment) > 255:
                continue
            stack.append((start + length, path + [segment]))
    return res

medium

A. Line missing check for segments with leading zeros

B. Line checking if segment length is 3 and value > 255

C. Line pruning based on remaining characters and segments

D. Line appending new segment to stack

Solution

1. Step 1: Identify missing validation

   The code lacks a check to reject segments with leading zeros like '00' or '01', which are invalid.

2. Step 2: Confirm other checks are correct

   Check for segment > 255 and pruning are present and correct; appending to stack is correct.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing leading zero check allows invalid IP segments [OK]

Hint: Leading zero check is mandatory to avoid invalid IPs [OK]

Common Mistakes:

• Forgetting leading zero validation
• Misplacing pruning conditions

4. Suppose the Expression Add Operators problem is modified so that digits can be reused any number of times to form expressions (i.e., unlimited reuse of digits in order). Which of the following algorithmic changes correctly adapts the backtracking solution to handle this variant without infinite loops or incorrect results?

hard

A. Remove the index increment in recursive calls to allow reuse, but add a visited set to avoid infinite loops

B. Keep the index increment as is, but allow substring splits to wrap around to the start of the string

C. Modify backtracking to not increment index after choosing a digit, but limit recursion depth to n to prevent infinite loops

D. Allow index to reset to zero after reaching the end, but prune expressions longer than a fixed length to avoid infinite recursion

Solution

1. Step 1: Understand digit reuse impact

   Allowing reuse means the index does not always increment; digits can be chosen repeatedly, risking infinite recursion.

2. Step 2: Prevent infinite loops

   Not incrementing index requires limiting recursion depth (e.g., max length n) to avoid infinite loops while exploring repeated digits.

3. Step 3: Evaluate options

   Modify backtracking to not increment index after choosing a digit, but limit recursion depth to n to prevent infinite loops correctly limits recursion depth while allowing reuse; others either cause infinite loops or incorrect pruning.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Limiting recursion depth prevents infinite loops with reuse [OK]

Hint: Limit recursion depth when digits can be reused [OK]

Common Mistakes:

• Forgetting to limit recursion depth causes infinite loops

5. Suppose you want to generate all permutations of an array where elements can be repeated any number of times (i.e., unlimited reuse of elements). Which modification to the standard backtracking approach is correct?

hard

A. Remove the used array entirely and allow elements to be chosen multiple times at each recursion level

B. Use the same backtracking with a used array but reset used[i] to false only after the entire recursion finishes

C. Use in-place swapping but skip swapping elements that have been used before in the current recursion path

D. Generate permutations normally and then filter out duplicates after generation

Solution

1. Step 1: Understand the problem variant

   Elements can be reused unlimited times, so no need to track usage.

2. Step 2: Modify backtracking accordingly

   Removing the used array allows choosing any element at each recursion level multiple times, generating permutations with repetition.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Allowing repeated choices without usage tracking fits unlimited reuse [OK]

Hint: Unlimited reuse means no used array needed [OK]

Common Mistakes:

• Keeping used array causes missing permutations or incorrect pruning