题目

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
示例:

  1. 输入: "25525511135"
  2. 输出: ["255.255.11.135", "255.255.111.35"]

答案

#
# @lc app=leetcode.cn id=93 lang=python3
#
# [93] 复原IP地址
#


# @lc code=start
class Solution:

    def restoreIpAddresses(self, s):

        if len(list(s)) < 4:
            return []
        tempL = []
        res = []

        def helper(s, index, level):
            if level == 5 or index == len(s) - 1:
                if level == 5 and index == len(s) - 1:  # 如果到了第五组，而且下标到了最后了终止
                    res.append('.'.join(tempL))
                    return res
                return res

            for i in range(1, 4):
                x = s[index + 1:index + 1 + i]
                if (x and int(x) < 256) and (x == '0' or not x[0:1] == '0'):
                    tempL.append(x)
                    helper(s, index + i, level + 1)
                    tempL.pop()

        helper(s, -1, 1)
        return res



# @lc code=end

Note

dfs+回溯
终止条件需要注意下