题解 | #数字字符串转化成IP地址#

数字字符串转化成IP地址, 回溯

相当于是找满足IP要求的数字字符组排列，最容易想到的就是用回溯
基本要素1，终止条件：如果遍历到字符串末尾或者找出的字段数已经超过4
基本要素2：元素选择：在某一个位置，可以选一个数作为IP地址的一个字段，也可以选两个数作为IP地址的一个字段，但第一位数不能是0，还可以选三个数作为IP地址的一个字段，但第一位数不能是0，且三位数不大于255。
基本要素3：递推关系，如果当前字段选了一个数s[idx]，那下一个字段就从s[idx+1]开始选，形成子问题。如果当前字段选了两个数s[idx：idx+2]，那下一个字段就从s[idx+2]开始选，形成子问题。如果当前字段选了三个数s[idx：idx+3]，那下一个字段就从s[idx+3]开始选，形成子问题。

class Solution:
    def restoreIpAddresses(self , s: str) -> List[str]:
        path = []
        res = []
        def backTracking(s, idx):
            if len(path)>4 or idx >= len(s):
                if len(path) == 4:
                    res.append('.'.join(path[:]))
                return 
            # 一位数
            path.append(s[idx])
            backTracking(s, idx+1)
            #两位数，首位不能为零
            if idx+1 < len(s) and s[idx]!='0':
                path[-1] = path[-1]+s[idx+1]
                backTracking(s, idx+2)
                # 三位数
                if idx+2 < len(s) and 0< int(s[idx:idx+3])<=255:
                    path[-1] = path[-1]+s[idx+2]
                    backTracking(s, idx+3)
            path.pop()
        backTracking(s, 0)
        return res