leetcode93 Restore IP Addresses

原文地址：https://leetcode.com/problems/restore-ip-addresses/

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

A valid IP address consists of exactly four integers (each integer is between 0 and 255) separated by single points.

Example:
Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        def backtrack(s,ip,ips,times):
            if times == 4 and (not s):
                ips.append(ip[1:])
            for i in range(1, 4):
                if i <= len(s):
                    if len(s[:i]) > 1 and s[0] == "0":
                        break
                    elif int(s[:i]) <= 255:
                        backtrack(s[i:], ip + "." + s[:i], ips, times+1)
            return
        
        if len(s) > 12 or len(s) < 4: return []
        ips = []
        backtrack(s,"",ips,0)
        return ips