0093._restore_ip_addresses.md

93. Restore IP Addresses

难度: Medium

刷题内容

原题连接

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

内容描述

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"]

解题方案

思路 1 - 时间复杂度: O(2^N)- 空间复杂度: O(1)******

首先，我们s的长度必须在4到12之间才可以，不然这个ip不可能合法

然后再写一个check ip是否合法的函数

然后对于我们的s，选择三个位置插入3个'.'构造一个ip，合法的ip放入结果中

beats 40.54%

class Solution:
    def restoreIpAddresses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        if len(s) > 12 or len(s) < 4:
            return []
        
        def isValid(ip):
            if ip.count('.') != 3:
                return False
            lst = ip.split('.')
            for num in lst:
                if not num or int(num) > 255 or (len(num) > 1 and num[0] == '0'):
                    return False
            return True
        
        self.res = []
        def helper(cur, idx, cnt):
            if cnt == 3:
                if isValid(cur):
                    self.res.append(cur)
                return
            if idx > len(cur) - 1:
                return
            helper(cur[:idx] + '.' + cur[idx:], idx + 2, cnt+1)
            helper(cur, idx+1, cnt)
            
        helper(s, 0, 0)
        return self.res