Practice › Recursion & Backtracking
Palindrome Partitioning
Medium · Recursion & Backtracking · Asked at Amazon, Google, Microsoft, Bloomberg
Split the string into pieces so that every piece is a palindrome. Print the number of ways, then every partition on its own line (pieces separated by spaces). List the partitions in the order a backtracking search produces them when it always tries the shorter first piece first.
Input
A single lowercase string s.
Output
The count, then the partitions.
Constraints
- 1 ≤ |s| ≤ 12
For each prefix that is a palindrome, take it as the first piece and recurse on the rest.
Example 1
Input
aab
Output
2 a a b aa b
Example 2
Input
a
Output
1 a
Hints
- Choose the first piece: try every prefix that is a palindrome, shortest first.
- Recurse on the rest of the string; when nothing is left, the pieces chosen so far form one partition.
Approach
go(start, pieces): if start == n, record the partition. Otherwise for end from start + 1 to n, if s[start..end) is a palindrome, push it and recurse from end, then pop. Trying shorter pieces first gives exactly the required order. For speed you can precompute isPal[i][j] with DP, but with |s| ≤ 12 a direct check is fine.
Complexity: O(2^n · n) time · O(n) recursion depth
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
string s;
vector<string> pieces, out;
bool isPal(int l, int r) {
while (l < r)
if (s[l++] != s[r--]) return false;
return true;
}
void go(int start) {
if (start == (int)s.size()) {
string line;
for (size_t i = 0; i < pieces.size(); i++) line += (i ? " " : "") + pieces[i];
out.push_back(line);
return;
}
for (int end = start; end < (int)s.size(); end++) {
if (!isPal(start, end)) continue;
pieces.push_back(s.substr(start, end - start + 1));
go(end + 1);
pieces.pop_back();
}
}
int main() {
cin >> s;
go(0);
cout << out.size() << "\n";
for (auto &l : out) cout << l << "\n";
return 0;
}Python solution
s = input().strip()
out = []
def go(start, pieces):
if start == len(s):
out.append(" ".join(pieces))
return
for end in range(start + 1, len(s) + 1):
piece = s[start:end]
if piece == piece[::-1]:
go(end, pieces + [piece])
go(0, [])
print(len(out))
print("\n".join(out))Java solution
import java.util.*;
public class Main {
static String s;
static List<String> out = new ArrayList<>();
static boolean isPal(int l, int r) {
while (l < r)
if (s.charAt(l++) != s.charAt(r--)) return false;
return true;
}
static void go(int start, String pieces) {
if (start == s.length()) {
out.add(pieces);
return;
}
for (int end = start; end < s.length(); end++) {
if (!isPal(start, end)) continue;
String piece = s.substring(start, end + 1);
go(end + 1, pieces.isEmpty() ? piece : pieces + " " + piece);
}
}
public static void main(String[] args) {
s = new Scanner(System.in).next();
go(0, "");
StringBuilder sb = new StringBuilder();
sb.append(out.size()).append('\n');
for (String l : out) sb.append(l).append('\n');
System.out.print(sb);
}
}Solve Palindrome Partitioning online · All practice problems