93. Restore IP Addresses.md

93. Restore IP Addresses

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

solution

# 分割类回溯

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        path = []
        res = []
        self.dfs(s, path, res, start=0)
        return res

    def dfs(self, s, path, res, start):
        if start >= len(s) and len(path) == 4:
            res.append('.'.join(path[:]))

        for i in range(start, len(s)):
            temp = s[start: i+1]
            if len(temp) > 1 and temp[0] == '0':
                continue
            elif int(temp) > 255:
                continue
            elif len(path) > 3:
                break
            else:
                path.append(temp)
                self.dfs(s, path, res, i+1)
                path.pop()

时间复杂度：O(3^4)
空间复杂度：O(1)