Restore IP Addresses

📋

Restore IP Addresses

Edge cases:

</>

IDE

def restore_ip_addresses(s: str) -> list:public List<String> restoreIpAddresses(String s)vector<string> restoreIpAddresses(string s)function restoreIpAddresses(s)

def restore_ip_addresses(s: str) -> list:
    # Write your solution here
    pass

class Solution {
    public List<String> restoreIpAddresses(String s) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
#include <string>
using namespace std;

vector<string> restoreIpAddresses(string s) {
    // Write your solution here
    return {};
}

function restoreIpAddresses(s) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: ["255.255.111.35", "255.255.11.135", "255.255.111.135"]Including segments longer than 3 digits or not pruning segments > 255.✅ Add condition to skip segments longer than 3 or with integer value > 255.

Wrong: ["0.0.0.0", "00.0.0.0"]Allowing segments with leading zeros like '00'.✅ Reject segments starting with '0' unless segment is exactly '0'.

Wrong: ["1.0.10.23", "1.0.102.3", "10.1.0.23", "10.10.2.3"]Missing some valid IPs due to incomplete backtracking or pruning too early.✅ Ensure backtracking explores all segment length options 1 to 3 and validates each segment.

Wrong: ["255.255.255.256"]Not checking upper bound of 255 for segments.✅ Add check to reject segments with integer value > 255.

Wrong: ["0.10.0.10", "0.100.1.0", "0.01.0.10"]Allowing segments with leading zeros like '01'.✅ Reject segments starting with '0' and length > 1.

✓

Test Cases

Focus on handling inputs too short or too long to form valid IPs.

Pay attention to segment validation rules and tricky leading zero cases.

Optimize your backtracking with pruning to handle large inputs efficiently.

t1_01basic

Input{"s":"25525511135"}

Expected["255.255.11.135","255.255.111.35"]

⏱ Performance - must finish in 2000ms

The string can be split into these two valid IP addresses by placing dots at appropriate positions.

💡 Try splitting the string into exactly 4 parts and check each part's validity.

💡 Check that each segment is between 0 and 255 and does not have leading zeros unless it is '0'.

💡 Use backtracking to explore all possible splits of length 1 to 3 for each segment.

Why it failed: Failed to generate all valid IPs or included invalid segments (leading zeros or >255). Fix by validating each segment strictly before recursion.

✓ Correctly generated all valid IP addresses for the canonical example.

t1_02basic

Input{"s":"101023"}

Expected["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

⏱ Performance - must finish in 2000ms

Multiple valid IP addresses can be formed by splitting the string into 4 valid segments.

💡 Consider all splits with segments of length 1 to 3 and validate each segment.

💡 Watch out for segments with leading zeros which are invalid except '0' itself.

💡 Backtrack by choosing segment lengths and prune invalid paths early.

Why it failed: Missed some valid IPs or included invalid segments with leading zeros or out-of-range values. Fix by pruning invalid segments and exploring all splits.

✓ Correctly found all valid IP addresses for the given input.

t2_01edge

Input{"s":""}

Expected[]

⏱ Performance - must finish in 2000ms

Empty input string cannot form any valid IP address.

💡 Check if the input length is less than 4 and return empty immediately.

💡 No segments can be formed from an empty string.

💡 Add a base case to handle empty input to avoid unnecessary recursion.

Why it failed: Returned non-empty result or error on empty input. Fix by adding a length check at start to return empty list if input length < 4.

✓ Correctly returned empty list for empty input.

t2_02edge

Input{"s":"1"}

Expected[]

⏱ Performance - must finish in 2000ms

Input length less than 4 cannot form a valid IP address with 4 segments.

💡 Check input length before processing; if less than 4, no valid IPs exist.

💡 Segments must total exactly 4; too few digits means no solution.

💡 Return empty list early for inputs shorter than 4 characters.

Why it failed: Returned invalid IPs or error for input shorter than 4. Fix by validating input length before recursion.

✓ Correctly returned empty list for single-digit input.

t2_03edge

Input{"s":"0000"}

Expected["0.0.0.0"]

⏱ Performance - must finish in 2000ms

All segments are '0', which is valid; no leading zeros issue here.

💡 Segments of '0' are valid but '00' or '01' are invalid.

💡 Check that segments with length > 1 do not start with '0'.

💡 Allow segment '0' but reject segments starting with '0' and longer than 1.

Why it failed: Rejected valid '0' segments or accepted invalid leading zero segments. Fix by allowing '0' but disallowing leading zeros in longer segments.

✓ Correctly handled segments with zero values.

t2_04edge

Input{"s":"1234567890123"}

Expected[]

⏱ Performance - must finish in 2000ms

Input length greater than 12 cannot form valid IP addresses since max 3 digits per segment and 4 segments.

💡 Check input length before processing; if greater than 12, no valid IPs exist.

💡 Return empty list early for inputs longer than 12 characters.

💡 Avoid unnecessary recursion for impossible input lengths.

Why it failed: Returned non-empty result or error for input longer than 12. Fix by adding length check to return empty list if input length > 12.

✓ Correctly returned empty list for input longer than 12.

t3_01corner

Input{"s":"255255255255"}

Expected["255.255.255.255"]

⏱ Performance - must finish in 2000ms

Maximum valid IP address with all segments at upper boundary 255.

💡 Check that segments with value 255 are accepted but not greater.

💡 Validate segment integer value <= 255.

💡 Ensure pruning skips segments > 255 but includes 255 exactly.

Why it failed: Excluded segments equal to 255 or included segments > 255. Fix by using <= 255 condition in validation.

✓ Correctly handled segments at upper boundary.

t3_02corner

Input{"s":"010010"}

Expected["0.10.0.10","0.100.1.0"]

⏱ Performance - must finish in 2000ms

Tests handling of leading zeros and multiple valid splits.

💡 Segments starting with '0' must be exactly '0' to be valid.

💡 Avoid segments like '01' or '00' which are invalid.

💡 Backtrack carefully to prune invalid leading zero segments.

Why it failed: Accepted invalid segments with leading zeros or missed valid splits. Fix by strict leading zero checks and exploring all valid splits.

✓ Correctly handled leading zero constraints.

t3_03corner

Input{"s":"1111"}

Expected["1.1.1.1"]

⏱ Performance - must finish in 2000ms

Minimal valid IP with all segments length 1.

💡 Check that segments of length 1 are always valid if digit is 0-9.

💡 Avoid skipping valid short segments.

💡 Backtrack should consider segment lengths 1 to 3.

Why it failed: Missed valid IPs with all segments length 1. Fix by including segment length 1 in backtracking loop.

✓ Correctly generated IP with all single-digit segments.

t4_01performance

Input{"s":"12345678901234567890"}

Expectednull

⏱ Performance - must finish in 2000ms

Input length 20 (max constraint). Backtracking with pruning must complete within 2 seconds.

💡 Backtracking complexity is O(3^4) but pruning reduces calls.

💡 Avoid unnecessary recursion by pruning invalid segments early.

💡 Use memoization or iterative backtracking to optimize if needed.

Why it failed: Solution timed out due to exponential recursion without pruning. Fix by adding pruning for invalid segments and early termination.

✓ Solution completed within time limit using pruning and efficient backtracking.

Practice

1. You need to generate all combinations of balanced parentheses pairs for a given number n. Which algorithmic approach guarantees generating only valid sequences without generating invalid ones first?

easy

A. Brute force: generate all possible sequences of '(' and ')' of length 2n, then filter valid ones

B. Backtracking with pruning: build sequences by adding '(' or ')' only when it keeps the sequence valid

C. Greedy approach: always add '(' until n is reached, then add ')' to close all opened parentheses

D. Dynamic programming: count the number of valid sequences using Catalan number formula

Solution

1. Step 1: Understand problem constraints

   We want to generate all valid parentheses sequences without generating invalid ones first.

2. Step 2: Analyze approaches

   Brute force generates all sequences including invalid ones, greedy fails to generate all valid sequences, DP counts sequences but does not generate them. Backtracking with pruning adds '(' or ')' only when valid, thus generating only valid sequences.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Backtracking with pruning avoids invalid sequences [OK]

Hint: Backtracking prunes invalid sequences early [OK]

Common Mistakes:

• Thinking greedy can generate all valid sequences
• Confusing counting with generating sequences

2. The following code attempts to solve N-Queens using bitmask backtracking. Which line contains a subtle bug that can cause invalid solutions or missed solutions?

medium

A. Line extracting rightmost 1-bit as position

B. Line updating diag1 and diag2 with incorrect bit shifts in recursive call

C. Line computing available_positions with bitmask and negation

D. Line resetting board[row][col] to '.' after recursion

Solution

1. Step 1: Identify bit shift directions for diagonals

   diag1 (major diagonal) must be shifted left by 1, diag2 (minor diagonal) shifted right by 1 to reflect next row attacks.

2. Step 2: Check recursive call shifts

   The code incorrectly shifts diag1 right and diag2 left, reversing the attack directions, causing invalid pruning.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct diagonal shifts are diag1 << 1 and diag2 >> 1 [OK]

Hint: Diagonal attack masks must shift opposite directions each row [OK]

Common Mistakes:

• Swapping diag1 and diag2 shifts
• Not resetting board after recursion
• Incorrect bitmask negation

3. 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

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 problem. It is almost correct but contains one subtle bug. Identify the line causing the bug.

medium

A. Line where board[r][c] = temp is restored after recursion

B. Line where temp = board[r][c]

C. Line where directions are defined

D. Line missing board[r][c] = '#' to mark visited

Solution

1. Step 1: Identify missing visited marking

   The code does not mark the current cell as visited before recursive calls, allowing revisits.

2. Step 2: Understand impact of missing marking

   Without marking, dfs can revisit the same cell multiple times, causing incorrect matches or infinite loops.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Marking visited cells is essential to prevent reuse [OK]

Hint: Check if visited cells are marked before recursion [OK]

Common Mistakes:

• Forgetting to mark visited cells
• Restoring cell too early