NUHMAN.com

Introduction

LeetCode 93: Restore IP Addresses asks you to find all possible valid IP addresses that can be obtained from a string containing only digits. A valid IP address consists of four octets, separated by dots (i.e., "x.x.x.x"), where each octet is an integer between 0 and 255. Furthermore, no octet can have leading zeros unless the octet itself is zero.

This problem is a classic example of using backtracking to explore all possible ways to split a string into four valid segments that represent a valid IP address.

Problem Statement

Given a string containing only digits, restore all possible valid IP addresses that can be formed by splitting the string into exactly four valid segments. Each segment must be a number between 0 and 255, and it cannot have leading zeros.

Example:

go

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

In this example, the input string "25525511135" can be split into two valid IP addresses: "255.255.11.135" and "255.255.111.35".

Approach: Backtracking

Steps:

1. Base Case:
2. We need to split the string into four parts. If we have reached four parts and the entire string is used, we check whether the parts form valid segments (i.e., between 0 and 255, and no leading zeros unless the part is "0").
3. Backtracking:
4. We explore all possible ways to split the string by considering up to three digits for each segment (since each segment can have a maximum of three digits). We use backtracking to explore all possible ways of splitting the string into four parts.
5. Checking Validity:
6. For each part, we ensure:

• The part is between 0 and 255.
• The part doesn't have leading zeros unless it is exactly "0".

1. Final Answer:
2. We store all valid IP addresses in a result list and return it at the end.

Go Implementation

go

func restoreIpAddresses(s string) []string {
    var result []string
    
    if len(s) < 4 || len(s) > 12 {
        return result
    }

    var backtrack func(start int, path []string)

    // Helper function to check if a string is a valid segment
    isValid := func(segment string) bool {
        if len(segment) > 1 && segment[0] == '0' {
            return false
        }
        val := 0
        for i := 0; i < len(segment); i++ {
            val = val*10 + int(segment[i]-'0')
        }
        return val >= 0 && val <= 255
    }

    backtrack = func(start int, path []string) {
        // If we've reached 4 segments and used all characters, store the result
        if len(path) == 4 {
            if start == len(s) {
                result = append(result, path[0]+"."+path[1]+"."+path[2]+"."+path[3])
            }
            return
        }

        // Try all possible lengths for the next segment (1, 2, or 3 digits)
        for i := 1; i <= 3; i++ {
            if start+i > len(s) {
                break
            }

            segment := s[start : start+i]
            if isValid(segment) {
                backtrack(start+i, append(path, segment))
            }
        }
    }

    backtrack(0, []string{})
    return result
}

Explanation

1. Base Case and Edge Conditions:

• We first check if the length of the string s is between 4 and 12. If not, we return an empty result because it's impossible to form a valid IP address with fewer than 4 digits or more than 12 digits.

2. Backtracking:

• We use a helper function backtrack to explore all possible segmentations of the string s. The backtrack function keeps track of the current index (start) in the string and the segments we've already chosen (path).
• At each step, we try segments of lengths 1, 2, or 3 (since an IP address part can have up to 3 digits).
• We check if each segment is valid using the isValid helper function.

3. Validation:

• The isValid function ensures that:
• The segment is not longer than 3 digits.
• The segment is between 0 and 255.
• It does not contain leading zeros unless it is "0".

4. Final Result:

• If we have four valid segments and have used the entire string (start == len(s)), we form the IP address by joining the segments with dots and add it to the result list.

Time and Space Complexity

MetricComplexityTime ComplexityO(3^4)Space ComplexityO(1)

Where:

• Time Complexity: The backtracking approach explores all possible ways to split the string into four segments. In the worst case, we are considering up to 3 options (length 1, 2, or 3) for each of the four segments, leading to a complexity of O(3^4) (which is constant time in practice since we are dealing with at most four segments).
• Space Complexity: The space complexity is O(1) for storing intermediate results, excluding the space required for the final list of valid IPs. Since we're using a list to store the segments, the space complexity for each recursion call is constant.

Edge Cases

1. String too short or too long:

• If the string has fewer than 4 or more than 12 digits, it is impossible to form a valid IP address, so we return an empty list.
• Example: s = "123", s = "1234567890123"

1. Leading Zeros:

• Any segment that has leading zeros is invalid, except for the segment "0".
• Example: "0255" is invalid as "0255" has a leading zero.

1. Valid IP Address Example:

• Input: s = "25525511135"
• Output: ["255.255.11.135", "255.255.111.35"]

1. Edge Case with Maximum Length:

• Example: s = "255255255255"
• Output: ["255.255.255.255"]

Conclusion

LeetCode 93: Restore IP Addresses is a problem that involves string manipulation and backtracking. The challenge is to explore all possible ways of splitting a string of digits into valid IP address segments and handle cases such as leading zeros and out-of-range numbers.

The backtracking approach is an elegant solution for this problem, as it efficiently explores all possible segmentations while ensuring that only valid IP addresses are considered. With an O(3^4) time complexity and O(1) space complexity, the solution is both time-efficient and space-efficient, making it suitable for a wide range of input sizes.

This problem is an excellent exercise in string manipulation and recursive algorithm design.