LeetCode Restore IP Addresses：DFS + 回溯 + 剪枝還原 IP 地址

題目大意

給定純數字字符串 s，插入三個點分成四段，每段 0~255 且無前導零（除非單個 0），返回所有合法 IP 地址。
例："25525511135" → ["255.255.11.135","255.255.111.35"]。

DFS 回溯框架

• 狀態：start 當前段起始索引，path 已選段列表。
• 終止：path.size() == 4 且 start == s.length() → 加入結果。
• 剪枝：
  • 剩餘字符太多/太少：remaining > (4-path.size())*3 或 remaining < (4-path.size())。
  • 段值 > 255 或 前導零（長度>1 且首字符 '0'）。
• 嘗試長度 1~3 的子串作為當前段。

Java 實現

class Solution {
    List res = new ArrayList<>();
    List seg = new ArrayList<>();
    public List restoreIpAddresses(String s) {
        if (s.length() < 4 || s.length() > 12) return res;
        dfs(s, 0);
        return res;
    }
    void dfs(String s, int start) {
        if (seg.size() == 4) {
            if (start == s.length())
                res.add(seg.get(0)+"."+seg.get(1)+"."+seg.get(2)+"."+seg.get(3));
            return;
        }
        // 剪枝：剩餘長度不匹配
        int remain = s.length() - start;
        int need = 4 - seg.size();
        if (remain < need || remain > need * 3) return;
        for (int len = 1; len <= 3 && start+len <= s.length(); ++len) {
            String sub = s.substring(start, start+len);
            if (sub.length() > 1 && sub.charAt(0) == '0') continue; // 前導零
            int val = Integer.parseInt(sub);
            if (val > 255) continue;
            seg.add(val);
            dfs(s, start+len);
            seg.remove(seg.size()-1);
        }
    }
}

Python 實現

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        res, seg = [], []
        def dfs(start):
            if len(seg) == 4:
                if start == len(s):
                    res.append('.'.join(map(str, seg)))
                return
            remain = len(s) - start
            need = 4 - len(seg)
            if remain < need or remain > need * 3: return
            for l in range(1, 4):
                if start + l > len(s): break
                sub = s[start:start+l]
                if l > 1 and sub[0] == '0': continue
                val = int(sub)
                if val > 255: continue
                seg.append(val)
                dfs(start+l)
                seg.pop()
        dfs(0)
        return res

複雜度

• 時間：O(1) —— 固定 4 段，每段 ≤3 位，總狀態數 ≤ 3⁴ = 81，常數級。
• 空間：O(1) 遞歸深度 4 + 結果輸出。

總結

本題是「定長分段 + 合法性約束」的標準回溯題。關鍵技巧：長度剪枝 + 前導零檢查 + 數值上限 255。同模板解決 LeetCode 93、字符串分割類問題。