DFS

93. Restore IP Addresses

A DFS solution.

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        res = []
        def valid(s):
            if len(s)==2:return 10<=int(s)<=99
            if len(s)==3:return 100<=int(s)<=255
        if len(s)>12:return []
        def dfs(s, hist):
            if not s:
                if len(hist)==4:
                    res.append('.'.join(hist))
                return
            if len(s)>=3:
                if valid(s[:3]):
                    dfs(s[3:], hist+[s[:3]])
            if len(s)>=2:
                if valid(s[:2]):
                    dfs(s[2:], hist+[s[:2]])
            dfs(s[1:], hist+[s[:1]])
        dfs(s, [])
        return res

It is slow and inefficient in memory using

Runtime: 44 ms, faster than 14.14% of Python3 online submissions for Restore IP Addresses.
Memory Usage: 14 MB, less than 5.56% of Python3 online submissions for Restore IP Addresses.

Can we do better?

I didn’t find any :(