分割回文串与复原IP地址

分割回文串（LeetCode 131）

将字符串分割成若干子串，使每个子串都是回文串，返回所有分割方案。

public List<List<String>> partition(String s) {
    List<List<String>> res = new ArrayList<>();
    boolean[][] dp = precomputePalindromes(s);
    backtrack(s, 0, new ArrayList<>(), res, dp);
    return res;
}

// 预计算 dp[i][j] 表示 s[i..j] 是否回文
private boolean[][] precomputePalindromes(String s) {
    int n = s.length();
    boolean[][] dp = new boolean[n][n];
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i <= 1 || dp[i+1][j-1]);
        }
    }
    return dp;
}

private void backtrack(String s, int start, List<String> path,
                        List<List<String>> res, boolean[][] dp) {
    if (start == s.length()) {
        res.add(new ArrayList<>(path));
        return;
    }
    for (int end = start; end < s.length(); end++) {
        if (dp[start][end]) {
            path.add(s.substring(start, end + 1));
            backtrack(s, end + 1, path, res, dp);
            path.removeLast();
        }
    }
}

关键优化：用 DP 预处理回文，避免每次判断 O(n)，总时间降为 O(n · 2^n)。

分割回文串 II（LeetCode 132）

最少分割次数（返回数字而非列表），用 DP 而非回溯。

public int minCut(String s) {
    int n = s.length();
    boolean[][] dp = precomputePalindromes(s);
    int[] cuts = new int[n];
    for (int i = 0; i < n; i++) {
        if (dp[0][i]) { cuts[i] = 0; continue; }
        cuts[i] = i;    // 最多切 i 刀
        for (int j = 1; j <= i; j++) {
            if (dp[j][i]) cuts[i] = Math.min(cuts[i], cuts[j-1] + 1);
        }
    }
    return cuts[n-1];
}

复原IP地址（LeetCode 93）

给定只含数字的字符串，还原所有有效IP地址。

public List<String> restoreIpAddresses(String s) {
    List<String> res = new ArrayList<>();
    backtrack(s, 0, 0, new StringBuilder(), res);
    return res;
}

private void backtrack(String s, int start, int part,
                        StringBuilder cur, List<String> res) {
    if (part == 4 && start == s.length()) {
        res.add(cur.toString().substring(0, cur.length() - 1));  // 去掉末尾'.'
        return;
    }
    if (part == 4 || start == s.length()) return;

    for (int len = 1; len <= 3 && start + len <= s.length(); len++) {
        String seg = s.substring(start, start + len);
        // 前导零 & 超出255 剪枝
        if (seg.length() > 1 && seg.charAt(0) == '0') break;
        if (Integer.parseInt(seg) > 255) break;
        cur.append(seg).append('.');
        backtrack(s, start + len, part + 1, cur, res);
        cur.delete(cur.length() - len - 1, cur.length());
    }
}

总结