Problem statement

https://leetcode.com/problems/restore-ip-addresses/

Solution

One possible solution is to use dfs with backtracking. Another way is to split string into 4 parts, for example using combinations function and check each part.

Complexity

Time complexity is $\mathcal{O}(t^3)$, where $t$ is length of s, because we choose $3$ combinations out of $t$. Space complexity is potentially the same.

class Solution:
    def restoreIpAddresses(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