93-复原ip地址

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

---

示例

输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]

---

解法

核心思想：回溯算法：利用分割4次之后剩余的字符串是否为空，来界定是不是有效的结果

count记录分割次数, ip记录当前的字符串, s记录剩余字符串

注意：分割一次加一个“.”，最后会多出一个点号

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        res = []
        # count记录分割次数, ip记录当前的字符串, s记录剩余字符串
        def backtrack(count, ip, s):
            if count == 4:
                if s=="": # 最后面会有个点号
                    res.append(ip[:-1])
                return
            if len(s) > 0: # 需考虑[0.0.0.0]的情况
                backtrack(count + 1, ip + s[:1] + ".", s[1:])
            if len(s) > 1 and s[0] != "0":
                backtrack(count + 1, ip + s[:2] + ".", s[2:])
            if len(s) > 2 and s[0] != "0" and int(s[:3]) < 256:
                backtrack(count + 1, ip + s[:3] + ".", s[3:])
                
        backtrack(0, "", s)
        return res

---

相关信息

LeetCode：Discussion | Solution