leetcode [93] 复原IP地址

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

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

有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 ‘.’ 分隔。

示例:

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

思路：dfs，注意，分割时要判断00，000等情况，方法为转数字转字符串和当前值是否相同。

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        ans = []
        def dfs(s, part, prev):
            if part == 0:
                if s == '': 
                    ans.append(prev[:-1])
                return
            for i in range(1, min(len(s) + 1, 4)):
                if 0 <= int(s[:i]) <= 255 and str(int(s[:i])) == s[:i]:
                    dfs(s[i:], part - 1, prev + s[:i] + '.')
        dfs(s, 4, '') 

        return ans