LeetCode 93 Restore IP Addresses：回溯分治生成合法 IP

題目簡介

給定純數字字符串，插入三個 '.' 分割成 4 段，每段 0-255 無前導零（除單個 0），輸出所有合法 IP 地址。如 "25525511135" → ["255.255.11.135","255.255.111.35"]。

解題思路：回溯 + 剪枝

遞歸函數 dfs(pos, seg, path)：

• pos：當前處理到字符串位置。
• seg：已分割段數（0~3）。
• path：當前構建的 IP 字符串（含 '.')。

每段嘗試長度 1~3：

1. 若剩餘字符長度 > (4-seg)*3 或 < (4-seg) 剪枝。
2. 取子串，若長度>1 且首字符為 '0' 跳過；若值 > 255 跳過。
3. 遞歸下一段，seg+1，path 加上段和 '.'。
4. 若 seg==4 且 pos==len，去掉末尾 '.' 加入答案。

代碼實現

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> res; string path;
        dfs(s, 0, 0, path, res);
        return res;
    }
    void dfs(string &s, int pos, int seg, string &path, vector<string> &res) {
        if (pos == s.size() && seg == 4) {
            res.push_back(path.substr(0, path.size()-1));
            return;
        }
        if (s.size() - pos > 3*(4-seg)) return; // 剪枝：剩餘太長
        for (int len = 1; len <= 3 && pos+len <= s.size(); len++) {
            if (len > 1 && s[pos] == '0') continue; // 前導零
            int val = stoi(s.substr(pos, len));
            if (val > 255) continue;
            int oldSize = path.size();
            path += s.substr(pos, len) + ".";
            dfs(s, pos+len, seg+1, path, res);
            path.resize(oldSize);
        }
    }
};

複雜度分析

固定 4 段，每段最多 3 種長度，總狀態數常數級，極快。