LeetCode LCR 086. 分割回文串

Categories:

题目描述
思路分析
1. 解法一：回溯 + DP 预处理（推荐）
2. 解法二：回溯 + 中心扩展判断
相似题目

题目描述

✅ LCR 086. 分割回文串

思路分析

解法一：回溯 + DP 预处理（推荐）

核心思路：

先用动态规划预处理出 isPalin[i][j]，表示子串 s[i..j] 是否是回文串，预处理时间 O(n²)。

然后进行回溯：从位置 start 开始，枚举所有切割点 end，若 isPalin[start][end] 为真则将该子串加入当前路径，递归处理剩余部分。

当 start == n 时，说明整个字符串已被切分完毕，将当前路径加入结果集。

回溯时撤销最后一个子串，继续尝试更长的切割点。

预处理的核心状态转移：isPalin[i][j] = (s[i] == s[j]) && (j - i <= 2 || isPalin[i+1][j-1])。

复杂度分析：

时间复杂度：O(n · 2ⁿ)，其中 n 表示字符串长度。最坏情况下共有 2ⁿ 种分割方案，每种方案需要 O(n) 时间复制路径；预处理 DP 为 O(n²)，不影响总体量级。

空间复杂度：O(n²)，其中 n 表示字符串长度。DP 表格占用 O(n²)，递归调用栈深度为 O(n)。

class Solution {
    public List<List<String>> partition(String s) {
        int n = s.length();
        // 预处理回文表：isPalin[i][j] 表示 s[i..j] 是否是回文
        boolean[][] isPalin = new boolean[n][n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    isPalin[i][j] = j - i <= 2 || isPalin[i + 1][j - 1];
                }
            }
        }

        List<List<String>> result = new ArrayList<>();
        backtrack(s, 0, isPalin, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(
            String s,
            int start,
            boolean[][] isPalin,
            List<String> path,
            List<List<String>> result) {
        // 已遍历完整个字符串，记录当前分割方案
        if (start == s.length()) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int end = start; end < s.length(); end++) {
            // 仅当 s[start..end] 是回文时才继续递归
            if (!isPalin[start][end]) {
                continue;
            }
            path.add(s.substring(start, end + 1));
            backtrack(s, end + 1, isPalin, path, result);
            // 撤销选择，回溯
            path.remove(path.size() - 1);
        }
    }
}

func partition(s string) [][]string {
	n := len(s)
	// 预处理回文表：isPalin[i][j] 表示 s[i..j] 是否是回文
	isPalin := make([][]bool, n)
	for i := range isPalin {
		isPalin[i] = make([]bool, n)
	}
	for i := n - 1; i >= 0; i-- {
		for j := i; j < n; j++ {
			if s[i] == s[j] {
				isPalin[i][j] = j-i <= 2 || isPalin[i+1][j-1]
			}
		}
	}

	var result [][]string
	var path []string

	var backtrack func(start int)
	backtrack = func(start int) {
		// 已遍历完整个字符串，记录当前分割方案
		if start == n {
			tmp := make([]string, len(path))
			copy(tmp, path)
			result = append(result, tmp)
			return
		}
		for end := start; end < n; end++ {
			// 仅当 s[start..end] 是回文时才继续递归
			if !isPalin[start][end] {
				continue
			}
			path = append(path, s[start:end+1])
			backtrack(end + 1)
			// 撤销选择，回溯
			path = path[:len(path)-1]
		}
	}

	backtrack(0)
	return result
}

解法二：回溯 + 中心扩展判断

核心思路：

不预处理 DP 表格，直接在回溯过程中调用中心扩展函数判断子串是否为回文。

对于每个候选子串 s[start..end]，使用双指针从两端向中间收缩逐字符比较。

该方法省去了 O(n²) 的额外空间，代价是每次回文判断需要 O(n) 时间，总体复杂度不变但常数更小。

适合字符串较短或内存受限的场景。

复杂度分析：

时间复杂度：O(n · 2ⁿ)，其中 n 表示字符串长度。共有 2ⁿ 种分割方案，每次回文判断最坏 O(n)。

空间复杂度：O(n)，其中 n 表示字符串长度。仅需递归调用栈和路径列表，不需要额外的 DP 表格。

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        backtrack(s, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(
            String s,
            int start,
            List<String> path,
            List<List<String>> result) {
        // 已遍历完整个字符串，记录当前分割方案
        if (start == s.length()) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int end = start; end < s.length(); end++) {
            // 中心扩展判断 s[start..end] 是否是回文
            if (!isPalindrome(s, start, end)) {
                continue;
            }
            path.add(s.substring(start, end + 1));
            backtrack(s, end + 1, path, result);
            // 撤销选择，回溯
            path.remove(path.size() - 1);
        }
    }

    // 双指针判断 s[left..right] 是否为回文
    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

func partition(s string) [][]string {
	var result [][]string
	var path []string

	// 双指针判断 s[left..right] 是否为回文
	isPalindrome := func(left, right int) bool {
		for left < right {
			if s[left] != s[right] {
				return false
			}
			left++
			right--
		}
		return true
	}

	var backtrack func(start int)
	backtrack = func(start int) {
		// 已遍历完整个字符串，记录当前分割方案
		if start == len(s) {
			tmp := make([]string, len(path))
			copy(tmp, path)
			result = append(result, tmp)
			return
		}
		for end := start; end < len(s); end++ {
			// 中心扩展判断 s[start..end] 是否是回文
			if !isPalindrome(start, end) {
				continue
			}
			path = append(path, s[start:end+1])
			backtrack(end + 1)
			// 撤销选择，回溯
			path = path[:len(path)-1]
		}
	}

	backtrack(0)
	return result
}

相似题目

题目	难度	考察点
132. 分割回文串 II	困难	动态规划
1278. 分割回文串 III	困难	动态规划
1745. 分割回文串 IV	困难	动态规划
5. 最长回文子串	中等	动态规划、中心扩展
647. 回文子串	中等	动态规划、中心扩展
39. 组合总和	中等	回溯
46. 全排列	中等	回溯
93. 复原 IP 地址	中等	回溯、字符串

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/15789904