Description:

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

Example:

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

Solution:

NOTE: 注意用“str(int(s)) == s”去开头的0，eg. "010" 不能被当做 "10"
NOTE: string[0] != "0"不能去开头的0，因为0本身是符合的，但不满足这个条件

class Solution:
    def restoreIpAddresses(self, s: str,num = 4) -> List[str]:
        if len(s) < num or len(s) > num*3:
            return []
        if num == 1 and int(s) < 256 and str(int(s)) == s: # 只剩一个slot了
            return [s]
        
        ls = [s[:1],s[:2],s[:3]]
        result = []
        for i in range(3):
            head = ls[i]
            if int(head) > 255 or str(int(head)) != head: # 数字太大 或者 开头有0
                break
            if i+1 < len(s):
                for r in self.restoreIpAddresses(s[i+1:],num-1):
                    result.append(head+"."+r)
                    
        return result

Runtime: 36 ms, faster than 91.37% of Python3 online submissions for Restore IP Addresses.
Memory Usage: 13.3 MB, less than 25.00% of Python3 online submissions for Restore IP Addresses.