Problem statement

https://binarysearch.com/problems/IP-Address-Combinations/

Solution

Equal to Leetcode 0093. Restore IP Addresses.

Complexity

It is O(t^3) for time and space.

Code

class Solution:
    def solve(self, s):
        def check(p):
            return 0 <= int(p) < 256 and str(int(p)) == p
        
        ans = []
        if len(s) > 12: return ans
        for i, j, k in combinations(range(1, len(s)), 3):
            parts = [s[:i], s[i:j], s[j:k], s[k:]]
            if all(check(p) for p in parts):
                ans.append(".".join(parts))
         
        return ans