复原 IP 地址

本题解使用了递归回溯的方法来构建所有可能的有效IP地址。从字符串的开始位置出发，通过递归地尝试每一个可能的分段（最长为3个字符），并且每段数字必须在0到255之间。特别地，单个'0'可以作为一段，但是'0'不能作为其他数字的前缀。在每一步递归中，如果当前的部分字符串符合IP地址的一个段的要求，就将其加到当前正在构建的IP地址中。当字符串被完全使用并且构建的IP地址由四段组成时，这个地址就被认为是一个有效的IP地址。通过这种方式，递归函数遍历所有可能的分段方式，直到找到所有的有效IP地址。

时间复杂度: O(1)

空间复杂度: O(n)

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        def search(s, last):
            # Base case: if the string is empty
            if len(s) == 0:
                # Check if the constructed IP has exactly four parts
                if len(last.split('.')) == 5:
                    ans.append(last)
                return
            # If already have more than 4 parts, return
            if len(last.split('.')) > 4:
                return
            # Special handling for segments starting with '0'
            if s[0] == '0':
                search(s[1:], last + '.' + s[0])
            else:
                # Try all possible lengths (1 to 3) for the current segment
                for i in range(min(3, len(s))):
                    # Check if the segment is a valid integer less than or equal to 255
                    if int(s[:i + 1]) > 255:
                        continue
                    search(s[i + 1:], last + '.' + s[:i + 1])
        ans = []
        search(s, '')
        # Strip the leading '.' from the constructed IP addresses before returning
        return [a.lstrip('.') for a in ans]