个人网页主页_浙江大境软装设计_今日新闻最新消息_河南今日重大新闻

1. 题目来源

链接：93. 复原 IP 地址

前置题目：

题单：

• 待补充

2. 题目解析

一道经典的 dfs 问题，但是有很多可以剪枝的地方需要注意。具体的见代码注释即可。

主要思想和 子集 啥的，差不多，就是在两个字符之间填 “.” 进去做分割。看看能填几段，或者将此题理解成将字符串分成 4 段，判断是否构成合法 IP 也行。

---

• 时间复杂度：$O(2^n)$
• 空间复杂度：$O(n)$

---

func restoreIpAddresses(s string) []string {n := len(s)res := []string{}path := []string{}var dfs func(int)dfs = func(u int) {if len(path) > 4 {  // path 多于 4，则直接 return return}if u == n && len(path) == 4 {s := path[0]for i := 1; i < len(path); i ++ {s += "."s += path[i]                }if ip := net.ParseIP(s); ip != nil {res = append(res, s)}return}for i := u; i < len(s); i ++ {if s[u] == '0' && i - u > 1 {   // 2位及以上时，必须 无前缀 0return }if i + 1 - u > 3 {   // 必须是 1-3 位return}path = append(path, s[u:i+1])dfs(i + 1)path = path[:len(path) - 1]}}dfs(0)return res
}