Solution Explanation: Restore IP Addresses

This problem requires finding all valid IP addresses that can be formed by inserting dots into a given string containing only digits. A valid IP address consists of four integers separated by dots, each integer between 0 and 255 (inclusive) and without leading zeros.

The most efficient approach is using Depth-First Search (DFS) or backtracking. The algorithm explores all possible ways to split the input string into four parts, checking the validity of each part at each step.

Approach: DFS (Depth-First Search)

1. Base Cases:

   • If we've reached the end of the input string (i >= n) and we've successfully split the string into four parts (len(t) == 4), we've found a valid IP address. Add it to the result list.
   • If we've reached the end of the input string or we've already split the string into more than four parts, backtrack.

2. Recursive Step:

   • Iterate through possible segment lengths (1 to 3 digits) starting from the current index i.
   • For each segment length:
     • Extract the segment as a substring.
     • Check if the segment is valid (between 0 and 255, no leading zeros).
     • If valid, add the segment to the temporary IP address list t.
     • Recursively call dfs with the next index (j + 1).
     • Remove the segment from t (backtracking) to explore other possibilities.

Time and Space Complexity Analysis

• Time Complexity: O(34 * n) ≈ O(n). The algorithm explores at most 3 choices for each of the four segments of the IP address, and the length of the input string is n. The constant factor 34 is relatively small.
• Space Complexity: O(n). The space is dominated by the recursion stack depth, which is proportional to the length of the input string in the worst case. The temporary list t also takes O(1) space because the size of the list remains fixed at 4 segments.

Code Implementation (Python)

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        n = len(s)
        ans = []
 
        def isValid(segment):
            if not segment: return False
            if len(segment) > 1 and segment[0] == '0': return False
            return 0 <= int(segment) <= 255
 
        def backtrack(index, current_ip):
            if index == n and len(current_ip) == 4:
                ans.append(".".join(current_ip))
                return
 
            if index >= n or len(current_ip) >= 4:
                return
 
            for i in range(1, min(4, n - index + 1)):
                segment = s[index:index + i]
                if isValid(segment):
                    backtrack(index + i, current_ip + [segment])
        
        backtrack(0, [])
        return ans

Other language implementations (Java, C++, Go, TypeScript, C#) follow the same logic with minor syntax adjustments. The core algorithm remains the same depth-first search approach. The crucial part is the isValid function to ensure that each segment conforms to IP address rules.