Restore IP Address

93. 复原IP地址

分析

有效 IP 地址的要求
- 由 4 个整数组成（范围 0 ~ 255）
- 整数之间用 . 分隔
- 不能有前导 0（如 "01" 是非法的）
- 所有字符必须被使用
dfs 递归逻辑
- u：当前扫描到的字符索引
- k：当前已解析出的 IP 段数
- path：当前已拼接的 IP 地址（尚未去除最后一个 .）
- 递归终止条件：
  - u == s.size()：如果字符串已经完全遍历：
    - 如果 k == 4，说明成功找到一个 IP 地址，去掉最后一个 .，加入结果集 res
    - 否则，返回（分段不足 4 段）
  - 如果 k == 4 且 s 还未遍历完，返回
遍历 1 ~ 3 位
- 循环遍历 i = u 到 i < s.size()，每次尝试截取 1 ~ 3 位：
  - 若存在前导 0，停止搜索
  - 转换成整数 t：t = t * 10 + s[i] - '0'
  - 如果 t > 255，停止搜索（数字超出 IP 地址范围）
  - 递归调用 dfs，继续尝试下一段

时间复杂度

最多有 4 段，每段最多 3 种选择，时间复杂度 O(3^4)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


class Solution
{
public:
    std::vector<std::string> res;  // 存放所有合法 IP 地址

    void dfs(std::string& s, int u, int k, std::string path)
    {
        if (u == s.size())  // 如果字符串已遍历完
        {
            if (k == 4)  // 且正好分成了 4 段
            {
                path.pop_back();  // 去掉最后一个 '.'
                res.push_back(path);  // 加入结果集
            }
            return;
        }

        if (k == 4)  // 超过 4 段，直接返回
            return;

        for (int i = u, t = 0; i < s.size(); ++i)
        {
            if (i > u && s[u] == '0')  // 不能有前导 0
                break;

            t = t * 10 + s[i] - '0';  // 将字符转换成整数

            if (t > 255)  // 超出 255，直接停止
                break;

            dfs(s, i + 1, k + 1, path + std::to_string(t) + '.');  // 递归
        }
    }

    vector<string> restoreIpAddresses(string s)
    {
        dfs(s, 0, 0, "");
        return res;
    }
};