Restore Ip Addresses - Leetcode Solution

The Restore IP Addresses problem is a classic backtracking challenge on LeetCode. Given a string containing only digits, you need to return all possible valid IP address combinations that can be obtained by inserting dots (.) into the string.

The IP address format consists of four decimal numbers, each ranging from 0 to 255, separated by dots. Each segment must not have leading zeros unless it is exactly "0".

Problem Statement

LeetCode Problem: Restore IP Addresses
Difficulty: Medium
Link: LeetCode Restore IP Addresses

Example:

Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

The string "25525511135" can be segmented into two valid IP addresses: "255.255.11.135" and `“255.255.111.35”.

Key Challenges

1. Backtracking Constraint: We need to find all possible ways of placing three dots in the string to form four valid IP segments.
2. Range Constraint: Each segment must be between 0 and 255 and cannot have leading zeros.
3. Efficiency: We need an efficient way to explore all valid combinations without checking redundant or invalid ones.

Backtracking Solution

Backtracking is a natural fit for this problem because it allows us to explore all valid placements of dots and prune invalid ones as we progress.

Backtracking Logic:

• We start by placing dots in various positions, and for each placement, we check if the resulting segments are valid.
• If we find a valid IP (4 valid segments), we store it in the result list.
• If any segment is invalid or if we have more than four segments, we backtrack and try a different combination.

Backtracking Algorithm:

• Start at the first character and explore placing dots at different positions.
• Continue exploring until we have placed three dots.
• For each configuration, validate the resulting four segments.
• If valid, add the result to the final list.

Code Implementation in JavaScript:

function restoreIp(s) {
    const result = [];
    
    function backtrack(start, path) {
        // Base case: if we have 4 segments and we're at the end of the string, it's a valid IP.
        if (path.length === 4) {
            if (start === s.length) {
                result.push(path.join('.'));
            }
            return;
        }
        
        // Try all possible lengths for the next segment (1, 2, or 3 digits)
        for (let len = 1; len <= 3; len++) {
            if (start + len > s.length) break;
            
            const segment = s.slice(start, start + len);
            
            // Check if the segment is valid
            if (isValid(segment)) {
                path.push(segment); // Choose
                backtrack(start + len, path); // Explore
                path.pop(); // Un-choose (backtrack)
            }
        }
    }
    
    function isValid(segment) {
        if (segment.length > 1 && segment[0] === '0') return false; // No leading zeros
        return Number(segment) >= 0 && Number(segment) <= 255;
    }
    
    backtrack(0, []);
    return result;
}

Explanation:

1. Base Case: If we have found 4 valid segments and have processed the entire string, we add the IP address to the result list.
2. For Loop: We try every possible length (1 to 3) for the next segment.
3. Validation: We validate the segment by checking if it’s within the range 0 to 255 and ensure no leading zeros.
4. Backtracking: We recursively explore the next position in the string. If the current path is invalid, we backtrack by removing the last added segment.

Time Complexity:

The backtracking approach tries all possible combinations of placing 3 dots in the string. The time complexity is approximately $O(3^n)$, where n is the length of the string. This is because we can place a dot after each digit (except the last one), and for each segment, we can choose 1 to 3 digits.

Conclusion

The Restore IP Addresses problem is a classic example of how backtracking can efficiently explore the entire solution space for problems involving combinations or permutations. By breaking down the problem into manageable segments and recursively exploring all valid configurations, we can find all valid IP addresses that can be formed from the input string.

Using backtracking provides a straightforward and elegant way to solve this problem, and with a state diagram, we can better visualize the steps taken to reach the solution.