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.