LeetCode 131: Palindrome Partitioning (Backtracking with Palindrome DP Pruning)
LeetCode 131BacktrackingDynamic ProgrammingStringToday we solve LeetCode 131 - Palindrome Partitioning.
Source: https://leetcode.com/problems/palindrome-partitioning/
English
Problem Summary
Given a string s, split it into substrings so every substring is a palindrome, and return all possible palindrome partitions.
Key Insight
This is a path-enumeration problem on cut positions. At index start, try every end where s[start..end] is palindrome, push it to current path, recurse from end + 1, then backtrack.
Brute Force and Limitations
Brute force tries all cut combinations and checks palindrome by scanning substring every time, causing repeated work. We can precompute palindrome truth table isPal[i][j] to prune invalid branches instantly.
Optimal Algorithm Steps
1) Build isPal with DP: s[i] == s[j] and inner part palindrome.
2) DFS from start = 0.
3) For each end in [start..n-1], continue only if isPal[start][end] is true.
4) Add substring to path, recurse on end + 1, then pop.
5) When start == n, record one full partition.
Complexity Analysis
Precompute DP: O(n^2) time and space.
DFS enumeration: worst-case O(n · 2^n) outputs and transitions.
Common Pitfalls
- Forgetting to copy current path into answer (aliasing bug).
- Wrong DP fill order for isPal (must ensure inner state ready).
- Missing backtrack pop after recursion.
- Off-by-one in substring boundaries.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public List<List<String>> partition(String s) {
int n = s.length();
boolean[][] isPal = 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) && (j - i <= 2 || isPal[i + 1][j - 1])) {
isPal[i][j] = true;
}
}
}
List<List<String>> ans = new ArrayList<>();
Deque<String> path = new ArrayDeque<>();
dfs(0, s, isPal, path, ans);
return ans;
}
private void dfs(int start, String s, boolean[][] isPal, Deque<String> path, List<List<String>> ans) {
if (start == s.length()) {
ans.add(new ArrayList<>(path));
return;
}
for (int end = start; end < s.length(); end++) {
if (!isPal[start][end]) continue;
path.addLast(s.substring(start, end + 1));
dfs(end + 1, s, isPal, path, ans);
path.removeLast();
}
}
}func partition(s string) [][]string {
n := len(s)
isPal := make([][]bool, n)
for i := range isPal {
isPal[i] = make([]bool, n)
}
for i := n - 1; i >= 0; i-- {
for j := i; j < n; j++ {
if s[i] == s[j] && (j-i <= 2 || isPal[i+1][j-1]) {
isPal[i][j] = true
}
}
}
ans := [][]string{}
path := []string{}
var dfs func(int)
dfs = func(start int) {
if start == n {
copyPath := append([]string{}, path...)
ans = append(ans, copyPath)
return
}
for end := start; end < n; end++ {
if !isPal[start][end] {
continue
}
path = append(path, s[start:end+1])
dfs(end + 1)
path = path[:len(path)-1]
}
}
dfs(0)
return ans
}class Solution {
public:
vector<vector<string>> partition(string s) {
int n = s.size();
vector<vector<bool>> isPal(n, vector<bool>(n, false));
for (int i = n - 1; i >= 0; --i) {
for (int j = i; j < n; ++j) {
if (s[i] == s[j] && (j - i <= 2 || isPal[i + 1][j - 1])) {
isPal[i][j] = true;
}
}
}
vector<vector<string>> ans;
vector<string> path;
function<void(int)> dfs = [&](int start) {
if (start == n) {
ans.push_back(path);
return;
}
for (int end = start; end < n; ++end) {
if (!isPal[start][end]) continue;
path.push_back(s.substr(start, end - start + 1));
dfs(end + 1);
path.pop_back();
}
};
dfs(0);
return ans;
}
};class Solution:
def partition(self, s: str) -> list[list[str]]:
n = len(s)
is_pal = [[False] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
for j in range(i, n):
if s[i] == s[j] and (j - i <= 2 or is_pal[i + 1][j - 1]):
is_pal[i][j] = True
ans = []
path = []
def dfs(start: int) -> None:
if start == n:
ans.append(path[:])
return
for end in range(start, n):
if not is_pal[start][end]:
continue
path.append(s[start:end + 1])
dfs(end + 1)
path.pop()
dfs(0)
return ansvar partition = function(s) {
const n = s.length;
const isPal = Array.from({ length: n }, () => Array(n).fill(false));
for (let i = n - 1; i >= 0; i--) {
for (let j = i; j < n; j++) {
if (s[i] === s[j] && (j - i <= 2 || isPal[i + 1][j - 1])) {
isPal[i][j] = true;
}
}
}
const ans = [];
const path = [];
const dfs = (start) => {
if (start === n) {
ans.push([...path]);
return;
}
for (let end = start; end < n; end++) {
if (!isPal[start][end]) continue;
path.push(s.slice(start, end + 1));
dfs(end + 1);
path.pop();
}
};
dfs(0);
return ans;
};中文
题目概述
给定字符串 s，把它切分为若干子串，使得每个子串都是回文串，返回所有可行切分方案。
核心思路
这是“按切割点搜索路径”的问题。对于起点 start，尝试所有终点 end，只要 s[start..end] 是回文，就加入当前路径，递归处理后缀，再回溯。
暴力解法与不足
暴力法会枚举所有切法并反复扫描判断回文，重复计算很多。先用 DP 预处理 isPal[i][j] 后，DFS 可以快速剪枝。
最优算法步骤
1）先构建回文表 isPal：s[i] == s[j] 且内部区间为回文。
2）从 start = 0 开始 DFS。
3）遍历 end，仅当 isPal[start][end] 为真时继续。
4）把子串加入路径，递归到 end + 1，返回后回溯弹出。
5）当 start == n 时记录一组完整答案。
复杂度分析
DP 预处理：时间 O(n^2)，空间 O(n^2)。
DFS 枚举：最坏约 O(n · 2^n)。
常见陷阱
- 把路径引用直接放进答案，导致后续回溯污染结果。
- 回文 DP 的填表顺序不对，读到未计算状态。
- 递归返回后漏掉 pop。
- 子串边界 end + 1 写错。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public List<List<String>> partition(String s) {
int n = s.length();
boolean[][] isPal = 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) && (j - i <= 2 || isPal[i + 1][j - 1])) {
isPal[i][j] = true;
}
}
}
List<List<String>> ans = new ArrayList<>();
Deque<String> path = new ArrayDeque<>();
dfs(0, s, isPal, path, ans);
return ans;
}
private void dfs(int start, String s, boolean[][] isPal, Deque<String> path, List<List<String>> ans) {
if (start == s.length()) {
ans.add(new ArrayList<>(path));
return;
}
for (int end = start; end < s.length(); end++) {
if (!isPal[start][end]) continue;
path.addLast(s.substring(start, end + 1));
dfs(end + 1, s, isPal, path, ans);
path.removeLast();
}
}
}func partition(s string) [][]string {
n := len(s)
isPal := make([][]bool, n)
for i := range isPal {
isPal[i] = make([]bool, n)
}
for i := n - 1; i >= 0; i-- {
for j := i; j < n; j++ {
if s[i] == s[j] && (j-i <= 2 || isPal[i+1][j-1]) {
isPal[i][j] = true
}
}
}
ans := [][]string{}
path := []string{}
var dfs func(int)
dfs = func(start int) {
if start == n {
copyPath := append([]string{}, path...)
ans = append(ans, copyPath)
return
}
for end := start; end < n; end++ {
if !isPal[start][end] {
continue
}
path = append(path, s[start:end+1])
dfs(end + 1)
path = path[:len(path)-1]
}
}
dfs(0)
return ans
}class Solution {
public:
vector<vector<string>> partition(string s) {
int n = s.size();
vector<vector<bool>> isPal(n, vector<bool>(n, false));
for (int i = n - 1; i >= 0; --i) {
for (int j = i; j < n; ++j) {
if (s[i] == s[j] && (j - i <= 2 || isPal[i + 1][j - 1])) {
isPal[i][j] = true;
}
}
}
vector<vector<string>> ans;
vector<string> path;
function<void(int)> dfs = [&](int start) {
if (start == n) {
ans.push_back(path);
return;
}
for (int end = start; end < n; ++end) {
if (!isPal[start][end]) continue;
path.push_back(s.substr(start, end - start + 1));
dfs(end + 1);
path.pop_back();
}
};
dfs(0);
return ans;
}
};class Solution:
def partition(self, s: str) -> list[list[str]]:
n = len(s)
is_pal = [[False] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
for j in range(i, n):
if s[i] == s[j] and (j - i <= 2 or is_pal[i + 1][j - 1]):
is_pal[i][j] = True
ans = []
path = []
def dfs(start: int) -> None:
if start == n:
ans.append(path[:])
return
for end in range(start, n):
if not is_pal[start][end]:
continue
path.append(s[start:end + 1])
dfs(end + 1)
path.pop()
dfs(0)
return ansvar partition = function(s) {
const n = s.length;
const isPal = Array.from({ length: n }, () => Array(n).fill(false));
for (let i = n - 1; i >= 0; i--) {
for (let j = i; j < n; j++) {
if (s[i] === s[j] && (j - i <= 2 || isPal[i + 1][j - 1])) {
isPal[i][j] = true;
}
}
}
const ans = [];
const path = [];
const dfs = (start) => {
if (start === n) {
ans.push([...path]);
return;
}
for (let end = start; end < n; end++) {
if (!isPal[start][end]) continue;
path.push(s.slice(start, end + 1));
dfs(end + 1);
path.pop();
}
};
dfs(0);
return ans;
};
Comments