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

問題描述

給定只含數字的字符串 s，插入三個點將其分成四段，每段為 0~255 且無前導零（除非該段就是 "0"）。返回所有合法 IP 地址。

回溯框架

遞歸函數 backtrack(start, depth, path)：

• start：當前處理的起始索引。
• depth：已確定的段數（0~3）。
• path：當前構建的片段列表。

終止條件：depth == 4 且 start == len → 加入答案；depth == 4 或 start == len → 返回。

嘗試長度 1~3 的子串 seg = s.substr(start, len)：

1. 若 len > 1 且 seg[0]=='0' → 繼續（前導零非法）。
2. 轉換為整數 val，若 val > 255 → 繼續。
3. 將 seg 加入 path，遞歸 backtrack(start+len, depth+1, path)，回溯彈出。

關鍵優化與坑點

• 提前剪枝：剩餘字符數 remain = len - start，需滿足 4-depth ≤ remain ≤ 3*(4-depth)。
• 字符串拼接效率：用 vector 存片段，最後 join；或用單字符串 push_back/pop_back。
• C++ 中 tmpString += s[a] + s[b] + s[c] 會導致字符相加（ASCII 值相加）而非拼接，必須用 push_back 或構造函數 string(1, s[a]) + ...。

參考代碼 (C++ 優化版)

class Solution {
public:
    vector restoreIpAddresses(string s) {
        vector res;
        string path;
        function dfs = [&](int start, int depth) {
            if (depth == 4) {
                if (start == s.size()) res.push_back(path);
                return;
            }
            int remain = s.size() - start;
            if (remain < 4 - depth || remain > 3 * (4 - depth)) return;
            for (int len = 1; len <= 3; ++len) {
                if (start + len > s.size()) break;
                if (len > 1 && s[start] == '0') break; // leading zero
                int val = stoi(s.substr(start, len));
                if (val > 255) break;
                int oldSize = path.size();
                if (depth) path += '.';
                path += s.substr(start, len);
                dfs(start + len, depth + 1);
                path.resize(oldSize);
            }
        };
        dfs(0, 0);
        return res;
    }
};

複雜度

最多 3^4 = 81 種分割，每種驗證 O(1)，總時間 O(1)（常數上界），空間 O(1)（輸出不計）。

總結

• 經典回溯，搜索空間極小，重點在邊界條件與前導零處理。
• C++ 字符串拼接陷阱：char + char = int，切記用 push_back 或 substr。
• 剪枝條件 remain ∈ [seg_left, 3*seg_left] 大幅減少無效遞歸。