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. Consider the following bitmask-based backtracking code for n=4. After placing the first queen at row 0, column 1, what is the value of available_positions at row 1 (second recursive call)?

easy

A. 0b1010 (binary 10 decimal)

B. 0b1100 (binary 12 decimal)

C. 0b1001 (binary 9 decimal)

D. 0b1000 (binary 8 decimal)

Solution

1. Step 1: Trace first queen placement at row 0, col 1

   Position bitmask = 0b0010 (decimal 2). Update cols=0b0010, diag1=(0b0010)<<1=0b0100, diag2=(0b0010)>>1=0b0001.

2. Step 2: Compute available_positions at row 1

   available_positions = (0b1111) & ~(cols | diag1 | diag2) = 0b1111 & ~(0b0010 | 0b0100 | 0b0001) = 0b1111 & ~0b0111 = 0b1111 & 0b1000 = 0b1000 (decimal 8). The only available position is column 3 (bit 3).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Bitmask after first queen excludes cols 1, diag1 shifted left, diag2 shifted right [OK]

Hint: Bitmask tracks attacked columns and diagonals precisely [OK]

Common Mistakes:

• Miscomputing diagonal shifts
• Off-by-one in bit length
• Confusing cols with diag masks

2. What is the time complexity of the backtracking with bitmask optimization approach for counting beautiful arrangements of size n?

medium

A. O(n * n!)

B. O(n^2)

C. O(n * 2^n)

D. O(n!)

Solution

1. Step 1: Identify the search space

   The algorithm explores permutations of n numbers, which is n! in worst case.

2. Step 2: Consider pruning and bitmask usage

   Bitmask helps track used numbers efficiently, pruning invalid branches but the total number of recursive calls is proportional to n * n! because for each position, up to n choices are tried.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking explores permutations with n choices per position, leading to O(n * n!) complexity [OK]

Hint: Backtracking permutations with bitmask -> O(n * n!) time [OK]

Common Mistakes:

• Confusing bitmask with exponential 2^n complexity
• Assuming polynomial due to pruning

3. Identify the bug in the following code snippet for counting beautiful arrangements:

medium

A. Line with 'bit = 1 << num' bit shift

B. Line with 'if (used & bit) == 0' check

C. Line with 'if pos > n:' condition

D. Line with recursive call 'backtrack(pos + 1, used | bit)'

Solution

1. Step 1: Analyze bit shift operation

   Bitmask uses 0-based indexing, so bit for number num should be 1 << (num - 1), not 1 << num.

2. Step 2: Consequence of incorrect bit shift

   Incorrect bit shifts cause wrong bits to be set/checked, leading to missing or duplicate counts.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct bit shift is critical for accurate used-state tracking [OK]

Hint: Bit shifts must be zero-based for bitmask [OK]

Common Mistakes:

• Off-by-one bit shifts
• Forgetting to unmark used numbers

4. What is the time complexity of the optimal backtracking with Trie approach for Word Search II, given a board of size MxN and a list of words with maximum length L? Assume the Trie is already built.

medium

A. O(M * N * 4 * 3^(L-1)) due to pruning and adjacency constraints

B. O(M * N * 4^L * W), where W is the number of words

C. O(M * N * L^2) because each cell explores all prefixes

D. O(M * N * L) since each cell is visited once per character

Solution

1. Step 1: Identify branching factor in backtracking

   From each cell, up to 4 directions are possible initially, then up to 3 directions for subsequent steps due to no revisiting.

2. Step 2: Calculate complexity with pruning

   Trie pruning reduces unnecessary paths, so complexity is roughly O(M * N * 4 * 3^(L-1)) where L is max word length.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Matches known complexity from Trie + backtracking analysis [OK]

Hint: Branching factor reduces after first step due to visited constraints [OK]

Common Mistakes:

• Confusing W (number of words) as multiplicative factor in optimal approach.

5. Examine the following code snippet for the Word Search II problem. Which line contains a subtle bug that can cause incorrect results or infinite loops?

medium

A. Line: currNode = node.children.get(letter)

B. Line: Missing marking of board[r][c] as visited before recursion

C. Line: if currNode.word:

D. Line: board[r][c] = letter at the end

Solution

1. Step 1: Identify visited marking necessity

   Backtracking requires marking the current cell as visited (e.g., replacing letter with '#') to avoid revisiting the same cell in the current path.

2. Step 2: Locate missing visited marking

   The code lacks the line that marks board[r][c] as visited before recursive calls, causing revisits and potential infinite loops.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Without visited marking, recursion revisits same cells [OK]

Hint: Visited marking prevents revisiting same cell in recursion [OK]

Common Mistakes:

• Forgetting to mark visited cells or unmark after recursion.