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 are given a 2D grid of letters and a list of words. You need to find all words that can be formed by sequentially adjacent letters (horizontally or vertically) without reusing the same cell in a single word. Which algorithmic approach best guarantees an efficient solution for this problem?

easy

A. Use dynamic programming to store subproblems of partial word matches.

B. Use a greedy search that picks the next letter with the highest frequency in the grid.

C. Use backtracking combined with a Trie data structure to prune invalid prefixes early.

D. Search each word independently using DFS without any prefix pruning.

Solution

1. Step 1: Understand problem constraints

   The problem requires searching multiple words in a grid with adjacency and no reuse constraints, which is expensive if done naively.

2. Step 2: Identify efficient pruning technique

   Backtracking with a Trie allows pruning search paths early when no word prefix matches, avoiding redundant searches.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Trie pruning reduces search space drastically compared to naive DFS [OK]

Hint: Trie + backtracking prunes invalid prefixes early [OK]

Common Mistakes:

• Thinking greedy or DP alone can solve adjacency constraints efficiently.

2. Consider the following code snippet for the Word Search II problem using backtracking with a Trie. Given the board and words below, what is the content of the result list after the function completes? Board: [['o','a','a','n'], ['e','t','a','e'], ['i','h','k','r'], ['i','f','l','v']] Words: ["oath", "pea", "eat", "rain"]

easy

A. ["eat", "rain"]

B. ["pea", "rain"]

C. ["oath", "pea", "eat", "rain"]

D. ["oath", "eat"]

Solution

1. Step 1: Trace backtracking for "oath" and "eat"

   Starting from 'o' at (0,0), the path "o-a-t-h" exists, so "oath" is found. Similarly, "eat" is found starting at 'e' (1,0) following adjacency.

2. Step 2: Verify "pea" and "rain" are not found

   "pea" and "rain" cannot be formed due to missing adjacency or letters in the board.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Output matches expected found words [OK]

Hint: Only words with valid adjacency and prefix in Trie appear [OK]

Common Mistakes:

• Assuming all words appear regardless of adjacency.

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

1. Step 1: Understand reuse requirement

   Allowing reuse means digits can be chosen multiple times to build combinations of length n.

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

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

4. Final Answer:

   Option A -> Option A

5. 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
• Ignoring reuse in DP or sorting

4. If the problem changes so that numbers can be reused multiple times in the permutation (i.e., repetition allowed), which modification to the algorithm is correct?

hard

A. Use a greedy approach to pick the smallest available number at each step until length n is reached.

B. Use the same factorial-based approach but do not remove numbers from the list after selection.

C. Modify factorial computations to account for repeated elements and use a multiset permutation formula.

D. Generate all permutations with backtracking and stop when the k-th is found, since factorial indexing no longer applies.

Solution

1. Step 1: Understand repetition impact

   Allowing reuse breaks the factorial number system assumption because permutations count changes drastically.

2. Step 2: Identify correct approach

   Backtracking with early stop can generate permutations with repetition and find the k-th one, as direct factorial indexing is invalid.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Factorial indexing fails with repetition; backtracking is correct fallback [OK]

Hint: Factorial indexing requires unique elements; repetition breaks it [OK]

Common Mistakes:

• Trying to reuse factorial indexing without adjustment
• Ignoring repetition changes permutation count
• Assuming greedy works for k-th permutation with repetition

5. Suppose the Word Search problem is modified so that the same cell can be used multiple times in forming the word. Which modification to the backtracking algorithm correctly handles this change?

hard

A. Add a global visited set to track cells used in all paths

B. Keep marking visited cells but reset them after each recursion

C. Remove the in-place marking of visited cells to allow reuse

D. Use dynamic programming to store partial results and avoid recomputation

Solution

1. Step 1: Understand new constraint

   Cells can be reused multiple times, so marking visited cells to prevent reuse is no longer needed.

2. Step 2: Modify algorithm accordingly

   Removing in-place marking allows revisiting cells, correctly reflecting the relaxed constraint.

3. Step 3: Evaluate other options

   Keeping marking or using global visited set prevents reuse incorrectly; DP is not suitable here.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Removing visited marking enables cell reuse as required [OK]

Hint: Relaxing constraints often means removing pruning steps [OK]

Common Mistakes:

• Keeping visited marking, causing false negatives
• Adding unnecessary global state