0093. Restore IP Addresses.md

• 0093 - Restore IP Addresses.md
• 难度：Medium｜ 中等
• 相关知识点： String |Backtracking
• 题目链接：https://leetcode.com/problems/restore-ip-addresses/description/

A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros.

For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses, but "0.011.255.245", "192.168.1.312" and "[email protected]" are invalid IP addresses. Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. You are not allowed to reorder or remove any digits in s. You may return the valid IP addresses in any order.

Example 1:

Input: s = "25525511135" Output: ["255.255.11.135","255.255.111.35"] Example 2:

Input: s = "0000" Output: ["0.0.0.0"] Example 3:

Input: s = "101023" Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

Constraints:

1 <= s.length <= 20 s consists of digits only.

Solution 1

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        def min_(s, num):
            """
            计算每个阶段最小长度 如 "25525511135"
            e.g. "25525511135" -> ["255.255.11.135","255.255.111.35"] 每个.之间至少2个值

            """
            if len(s) == 3 * num:
                return 3
            elif len(s) > 3 * (num-1) + 1:
                return 2
            else:
                return 1
            
        def backtrack(start, path):
            if start == len(s) and len(path) == 4:
                result.append(".".join(path))
                return
            if len(path) >= 4:
                return

            for i in range(1, 4):
                l = min_(s[start:], 4-len(path))
                if i < l:
                    continue
                if start + i > len(s):
                    break
                part = s[start:start+i]
                
                #每个part最多3个值 如果某个部分只选少数元素作为一个part，那剩下的s分配part时会有多余的部分没办法分配
                if len(s[start + i:]) > (4 - len(path + [part]))*3:
                    continue
                 
                if (i == 1 or part[0] != '0') and 0 <= int(part) <= 255:
                    backtrack(start + i, path + [part])
       
        result = []
        backtrack(0, [])

        
        return result

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        def backtrack(start, path):
            if start == len(s) and len(path) == 4:
                result.append(".".join(path))
                return
            if len(path) >= 4:
                return
            for i in range(1, 4):
                if start + i > len(s):
                    break
                part = s[start:start+i]
                if len(s[start + i:]) > (4 - len(path))*3:
                    continue
                 
                if (i == 1 or part[0] != '0') and 0 <= int(part) <= 255:
                    backtrack(start + i, path + [part])
        
        result = []
        backtrack(0, [])
        return result

Solution 2

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        def is_valid(part):
            return len(part) == 1 or (part[0] != '0' and 0 <= int(part) <= 255)

        result = []
        for i in range(1, 4):
            for j in range(1, 4):
                for k in range(1, 4):
                    for l in range(1, 4):
                        if i + j + k + l == len(s):
                            part1 = s[:i]
                            part2 = s[i:i+j]
                            part3 = s[i+j:i+j+k]
                            part4 = s[i+j+k:]
                            if is_valid(part1) and is_valid(part2) and is_valid(part3) and is_valid(part4):
                                result.append(f"{part1}.{part2}.{part3}.{part4}")
        return result

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        def func1(s, num):
            if len(s) == 3 * num:
                return 3
            elif len(s) > 3 * (num-1) + 1:
                return 2
            else:
                return 1
        
        def func2(m_, num, s):
            return min(len(s)-m_*(num-1)+1, 4)

        def is_valid(part):
            return len(part) == 1 or (part[0] != '0' and 0 <= int(part) <= 255)

        result = []
        m_ = func1(s, 4)
       
        for i in range(m_, func2(m_, 4, s)):
            if m_ * 3 > len(s[i:]) > 3 * 3 :
                continue
            for j in range(m_, func2(m_, 3, s[i:])):
                if m_ * 2 > len(s[i+j:]) > 3 * 2 :
                    continue
                for k in range(m_, func2(m_, 2, s[i+j:])):
                    if i+j+k >= len(s) or  m_ * 1 > len(s[i+j+k:]) > 3 * 1 :  
                        continue
                    for l in range(m_, func2(m_, 1, s[i+j+k:])):
                        if i + j + k + l == len(s):
                            part1 = s[:i]
                            part2 = s[i:i+j]
                            part3 = s[i+j:i+j+k]
                            part4 = s[i+j+k:]
                            if is_valid(part1) and is_valid(part2) and is_valid(part3) and is_valid(part4):
                                result.append(f"{part1}.{part2}.{part3}.{part4}")
        return result