💡 The path now has three segments; one more segment is needed.
traverse
Pop state: start=8, path=['255', '255', '11']
The algorithm pops the state to explore the last segment starting at index 8.
💡 The last segment completes the IP address if valid.
Line:start, path = stack.pop()
💡 We are now choosing the final segment.
compare
Try segment length 3 at start=8: '135'
The algorithm tries the segment '135' starting at index 8 and validates it as the last segment.
💡 The last segment must consume the remaining characters and be valid.
Line:segment = s[start:start+length]
if (segment.startswith('0') and len(segment) > 1) or (length == 3 and int(segment) > 255):
continue
💡 A valid last segment completes the IP address.
insert
Add complete IP '255.255.11.135' to results
Since 4 segments are formed and the entire string is consumed, the algorithm adds '255.255.11.135' to the results.
💡 Collecting valid IP addresses is the goal of the algorithm.
Line:if len(path) == 4 and start == len(s):
res.append(".".join(path))
💡 Complete valid IP addresses are collected here.
traverse
Pop state: start=9, path=['255', '255', '111']
The algorithm pops the state to explore the last segment starting at index 9.
💡 Final segment exploration to complete IP.
Line:start, path = stack.pop()
💡 We are now choosing the final segment for the second valid IP.
compare
Try segment length 2 at start=9: '35'
The algorithm tries the segment '35' starting at index 9 and validates it as the last segment.
💡 The last segment must be valid and consume all remaining characters.
Line:segment = s[start:start+length]
if (segment.startswith('0') and len(segment) > 1) or (length == 3 and int(segment) > 255):
continue
💡 Valid last segments complete the IP address.
insert
Add complete IP '255.255.111.35' to results
The algorithm adds '255.255.111.35' to the results as a valid IP address with 4 segments covering the entire string.
💡 Collecting all valid IP addresses found.
Line:if len(path) == 4 and start == len(s):
res.append(".".join(path))
💡 All valid IP addresses are collected here.
from typing import List
def restore_ip_addresses(s: str) -> List[str]:
res = []
stack = [(0, [])] # (start index, path) # STEP 1
while stack:
start, path = stack.pop() # STEP 2, 5, 8, 11, 14, 16
if len(path) == 4: # STEP 13, 16
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): # STEP 3, 6, 9, 12, 15
if start + length > len(s):
break
segment = s[start:start+length]
if (segment.startswith('0') and len(segment) > 1) or (length == 3 and int(segment) > 255):
continue
stack.append((start + length, path + [segment])) # STEP 4, 7, 10
return res
if __name__ == "__main__":
test_input = "25525511135"
print(restore_ip_addresses(test_input))
📊
Restore IP Addresses - Watch the Algorithm Execute, Step by Step
Watching each segment choice and pruning decision helps you understand how the algorithm efficiently avoids invalid IP segments and collects valid addresses.
Step 1/16
·Active fill★Answer cell
enterings="25525511135"
Call Path (current → root)
restore_ip_addresses(s='25525511135')
Remaining
start=0, path=[]
choosings="25525511135"
Call Path (current → root)
restore_ip_addresses(s='25525511135')
Tried
start=0, path=[]
choosings="25525511135"
Call Path (current → root)
restore_ip_addresses(s='25525511135')
Tried
segment='2'segment='25'segment='255'
choosings="25525511135"
Call Path (current → root)
restore_ip_addresses(s='25525511135')
Tried
segment='2'segment='25'segment='255'
choosings="25525511135"
Call Path (current → root)
restore_ip_addresses(s='25525511135')
Tried
start=3, path=['255']
Partial: [255]
choosings="25525511135"
Call Path (current → root)
restore_ip_addresses(s='25525511135')
Tried
segment='2'segment='25'segment='255'
Partial: [255]
choosings="25525511135"
Call Path (current → root)
restore_ip_addresses(s='25525511135')
Tried
segment='2'segment='25'segment='255'
Partial: [255]
choosings="25525511135"
Call Path (current → root)
restore_ip_addresses(s='25525511135')
Tried
start=6, path=['255', '255']
Partial: [255, 255]
choosings="25525511135"
Call Path (current → root)
restore_ip_addresses(s='25525511135')
Tried
segment='11'segment='111'
Partial: [255, 255]
choosings="25525511135"
Call Path (current → root)
restore_ip_addresses(s='25525511135')
Tried
segment='11'segment='111'
Partial: [255, 255]
choosings="25525511135"
Call Path (current → root)
restore_ip_addresses(s='25525511135')
Tried
start=8, path=['255', '255', '11']
Partial: [255, 255, 11]
choosings="25525511135"
Call Path (current → root)
restore_ip_addresses(s='25525511135')
Tried
segment='135'
Partial: [255, 255, 11]
backtrackings="25525511135"
Call Path (current → root)
restore_ip_addresses(s='25525511135')
Tried
segment='135'
Partial: [255, 255, 11, 135]
Found 1: [255.255.11.135]
choosings="25525511135"
Call Path (current → root)
restore_ip_addresses(s='25525511135')
Tried
start=9, path=['255', '255', '111']
Partial: [255, 255, 111]
Found 1: [255.255.11.135]
choosings="25525511135"
Call Path (current → root)
restore_ip_addresses(s='25525511135')
Tried
segment='35'
Partial: [255, 255, 111]
Found 1: [255.255.11.135]
backtrackings="25525511135"
Call Path (current → root)
restore_ip_addresses(s='25525511135')
Tried
segment='35'
Partial: [255, 255, 111, 35]
Found 2: [255.255.11.135] [255.255.111.35]
Key Takeaways
✓ The algorithm uses a stack to iteratively explore all possible segmentations, avoiding recursion overhead.
This is hard to see from code alone because the stack manipulation and pruning logic are intertwined.
✓ Pruning based on remaining characters and segments drastically reduces the search space.
Visualizing pruning decisions clarifies why some paths are abandoned early.
✓ Valid segments must not start with zero unless they are '0', and must be <= 255, which guides segment validation.
Seeing each segment validation step helps understand these constraints concretely.
Practice
(1/5)
1. You need to partition a string into substrings such that every substring is a palindrome. Which algorithmic approach guarantees finding all possible palindrome partitions efficiently by pruning invalid partitions early?
easy
A. Backtracking that explores all substring partitions and checks palindrome validity dynamically
B. Dynamic programming that counts the number of palindromic substrings without generating partitions
C. Greedy approach that picks the longest palindrome substring at each step
D. Breadth-first search that generates partitions level by level without palindrome checks
Solution
Step 1: Understand problem requirements
The problem requires generating all palindrome partitions, not just counting or finding one.
Step 2: Identify suitable algorithm
Backtracking explores all partitions and prunes invalid ones by checking palindrome substrings dynamically, ensuring completeness and correctness.
Final Answer:
Option A -> Option A
Quick Check:
Backtracking with palindrome checks finds all partitions [OK]
Hint: Backtracking explores all partitions with palindrome pruning [OK]
Common Mistakes:
Assuming greedy longest palindrome picks all partitions
Confusing counting palindromes with generating partitions
Ignoring palindrome checks in BFS
2. Given the following code for palindrome partitioning, what is the final output when input string s = "aab" is passed to partition(s)?
def partition(s):
def is_palindrome(left, right):
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
def backtrack(start, path):
if start == len(s):
result.append(path[:])
return
for end in range(start, len(s)):
if is_palindrome(start, end):
path.append(s[start:end+1])
backtrack(end+1, path)
path.pop()
result = []
backtrack(0, [])
return result
easy
A. [["a", "a", "b"]]
B. [["a", "ab"], ["aa", "b"]]
C. [["a", "a", "b"], ["aa", "b"]]
D. [["aab"]]
Solution
Step 1: Trace backtrack calls for s="aab"
Start=0, path=[]; check substrings: "a" (palindrome), "aa" (palindrome), "aab" (not palindrome). Explore "a" -> backtrack(1, ["a"]), then "a" -> backtrack(2, ["a", "a"]), then "b" -> backtrack(3, ["a", "a", "b"]) adds ["a", "a", "b"] to result.
Step 2: Explore "aa" substring
From start=0, choose "aa" -> backtrack(2, ["aa"]), then "b" -> backtrack(3, ["aa", "b"]) adds ["aa", "b"] to result.
Final Answer:
Option C -> Option C
Quick Check:
Both partitions contain only palindromes and cover entire string [OK]
Hint: Trace recursion and palindrome checks carefully [OK]
Common Mistakes:
Including non-palindromic substrings like "ab"
Missing one valid partition
Returning partial partitions
3. 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
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".
Step 2: Confirm bug location
This missing check is critical and should be placed before parsing curr_str to avoid invalid expressions.
Final Answer:
Option A -> Option A
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
4. What is the time complexity of the optimal in-place next permutation algorithm for an input array of length n?
medium
A. O(n) because it scans the array a constant number of times
B. O(n log n) because it sorts the suffix after the pivot
C. O(n!) due to generating all permutations
D. O(n^2) because it swaps elements multiple times in nested loops
Solution
Step 1: Identify the main operations
The algorithm scans from the end to find the pivot (O(n)), then scans again to find the swap element (O(n)), and finally reverses the suffix (O(n)).
Step 2: Sum up the operations
All steps are linear scans or swaps, so total time complexity is O(n).
Final Answer:
Option A -> Option A
Quick Check:
No sorting or factorial generation involved, linear scans only [OK]
Hint: Next permutation scans array linearly multiple times [OK]
Common Mistakes:
Confusing suffix reversal with sorting
Assuming factorial due to permutations
5. Suppose the problem is modified so that digits can be repeated any number of times (reuse allowed), and you want to generate all letter combinations of length n from the given digits. Which modification to the algorithm correctly handles this reuse scenario?
hard
A. Modify backtracking to allow choosing the same digit multiple times by not incrementing the index after each choice until length n is reached
B. Sort digits and generate combinations by picking letters only once per digit
C. Use dynamic programming to store combinations of length k and build up to length n without reuse
D. Use the same iterative queue approach but do not advance the digit index; instead, for each combination, append letters from all digits repeatedly until length n is reached
Solution
Step 1: Understand reuse requirement
Allowing reuse means digits can be chosen multiple times to build combinations of length n.
Step 2: Identify correct approach
Backtracking can be modified to not increment the digit index after choosing a letter, allowing reuse until length n is reached.
Step 3: Why other options fail
Iterative queue approach as-is assumes fixed digit positions; DP without reuse does not handle repeated digits; sorting and picking once per digit ignores reuse.
Final Answer:
Option A -> Option A
Quick Check:
Backtracking with flexible index handles reuse elegantly [OK]
Hint: Backtracking index controls reuse by not advancing [OK]
Common Mistakes:
Trying to reuse digits in iterative approach without index control