LeetCode Restore IP Addresses：DFS 回溯恢復 IP 地址

LeetCode Restore IP Addresses：給定純數字字串，插入 3 個點分成 4 段，每段 0-255 且無前導零（除非單個 0），返回所有合法 IP 地址。

核心約束

• 4 段，每段長度 1-3
• 數值 0-255
• 無前導零："0" 合法，"01"、"00" 非法
• 字串長度 4-12，否則無解

DFS 回溯框架

void dfs(int seg, int idx, string& s, string& path, vector<string>& res) {
    if (seg == 4) {
        if (idx == s.size()) res.push_back(path.substr(0, path.size()-1)); // 去掉末尾 '.'
        return;
    }
    if (idx == s.size()) return; // 字串用盡但段數不足
    
    // 嘗試長度 1,2,3
    for (int len = 1; len <= 3 && idx + len <= s.size(); ++len) {
        string part = s.substr(idx, len);
        if (valid(part)) {
            int old_len = path.size();
            path += part + '.';
            dfs(seg + 1, idx + len, s, path, res);
            path.resize(old_len); // 回溯
        }
    }
}

bool valid(const string& s) {
    if (s[0] == '0') return s == "0"; // 前導零檢查
    int val = stoi(s);
    return val > 0 && val <= 255;
}

完整 AC 代碼 (C++)

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        if (s.size() < 4 || s.size() > 12) return res;
        string path;
        dfs(0, 0, s, path, res);
        return res;
    }
    
private:
    void dfs(int seg, int idx, const string& s, string& path, vector<string>& res) {
        if (seg == 4) {
            if (idx == s.size()) res.push_back(path.substr(0, path.size()-1));
            return;
        }
        if (idx == s.size()) return;
        
        for (int len = 1; len <= 3 && idx + len <= s.size(); ++len) {
            // 前導零快速剪枝
            if (len > 1 && s[idx] == '0') break;
            
            int val = 0;
            for (int i = 0; i < len; ++i) 
                val = val * 10 + (s[idx+i] - '0');
            if (val > 255) break; // 單調遞增，後續更大
            
            int old = path.size();
            path.append(s, idx, len);
            path.push_back('.');
            dfs(seg + 1, idx + len, s, path, res);
            path.resize(old);
        }
    }
};

關鍵優化技巧

1. 整數累積代替 substr+stoi：避免字串分配開銷
2. 前導零提前剪枝：len>1 && s[idx]=='0' → break
3. 數值上界剪枝：val > 255 → break（後續長度更大）
4. 路徑原地修改 + resize 回溯：避免字串拷貝
5. 長度預檢：4 ≤ n ≤ 12 直接返回空

複雜度分析

• 時間：O(1) — 搜索空間固定上界（3⁴ × 排列組合）
• 空間：O(1) 輸出不計，遞歸深度 4，路徑長度 ≤ 15

Java 版本參考

public class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        if (s == null || s.length() < 4 || s.length() > 12) return res;
        StringBuilder path = new StringBuilder();
        dfs(0, 0, s, path, res);
        return res;
    }
    
    void dfs(int seg, int idx, String s, StringBuilder path, List<String> res) {
        if (seg == 4 && idx == s.length()) {
            res.add(path.substring(0, path.length()-1));
            return;
        }
        if (seg == 4 || idx == s.length()) return;
        
        for (int len = 1; len <= 3 && idx + len <= s.length(); len++) {
            if (len > 1 && s.charAt(idx) == '0') break;
            int val = Integer.parseInt(s.substring(idx, idx+len));
            if (val > 255) break;
            
            int old = path.length();
            path.append(s, idx, idx+len).append('.');
            dfs(seg+1, idx+len, s, path, res);
            path.setLength(old);
        }
    }
}

總結

• 固定段數、固定長度範圍 → 回溯搜索空間極小
• 約束條件轉化為剪枝條件：前導零、數值上界、剩餘長度
• 字串操作優化：StringBuilder/原地修改、整數累積
• 經典 DFS 回溯模板：狀態參數、終止條件、選擇列表、狀態修改、遞歸、狀態恢復

此題是回溯算法入門的完美範例，展示了約束傳播、剪枝優化與工程級代碼實現的結合。