Problem
Given a string, split it into as few strings as possible such that each string is a palindrome.
Examples
Example 1
Input: "aab"
Output: ["aa", "b"]
Explanation: The string "aab" can be split into ["aa", "b"], where both "aa" and "b" are palindromes.
Example 2
Input: "racecarannakayak"
Output: ["racecar", "anna", "kayak"]
Explanation: The string "racecarannakayak" can be split into ["racecar", "anna", "kayak"], where each substring is a palindrome.
Solution
Method 1 - DP
To solve this problem, we can use dynamic programming to keep track of the minimum cuts needed to partition the string into palindromic substrings. Here’s the detailed approach:
Approach
- Dynamic Programming Table: Create a table
dp
wheredp[i]
represents the minimum number of cuts needed to partition the substrings[0:i+1]
into palindromic substrings. - Palindrome Table: Create a 2D table
palindrome
wherepalindrome[i][j]
isTrue
if the substrings[i:j+1]
is a palindrome. - Initialization: Initialize the
palindrome
table. Ifs[i] == s[j]
and the substring between them is also a palindrome, thenpalindrome[i][j]
isTrue
. - Filling DP Table: Iterate through the string to fill in the
dp
table using thepalindrome
table to determine the minimum cuts required. - Backtracking: Use the
dp
table to backtrack and find the palindromic substrings.
Code
Java
public class Solution {
public List<String> minCutPalindromes(String s) {
int n = s.length();
boolean[][] palindrome = new boolean[n][n];
int[] dp = new int[n];
for (int i = 0; i < n; i++) {
palindrome[i][i] = true;
}
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
if (s.charAt(i) == s.charAt(j)) {
palindrome[i][j] = (len == 2) || palindrome[i + 1][j - 1];
} else {
palindrome[i][j] = false;
}
}
}
for (int i = 0; i < n; i++) {
if (palindrome[0][i]) {
dp[i] = 0;
} else {
dp[i] = Integer.MAX_VALUE;
for (int j = 0; j < i; j++) {
if (palindrome[j + 1][i] && dp[j] + 1 < dp[i]) {
dp[i] = dp[j] + 1;
}
}
}
}
List<String> result = new ArrayList<>();
int index = n - 1;
while (index >= 0) {
for (int j = 0; j <= index; j++) {
if (palindrome[j][index] && (j == 0 || dp[j - 1] + 1 == dp[index])) {
result.add(0, s.substring(j, index + 1));
index = j - 1;
break;
}
}
}
return result;
}
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.minCutPalindromes("aab"));
System.out.println(solution.minCutPalindromes("racecarannakayak"));
System.out.println(solution.minCutPalindromes("abac"));
}
}
Python
class Solution:
def minCutPalindromes(self, s: str) -> List[str]:
n = len(s)
dp = [0] * n
palindrome = [[False] * n for _ in range(n)]
for i in range(n):
palindrome[i][i] = True
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
palindrome[i][j] = (length == 2) or palindrome[i + 1][j - 1]
else:
palindrome[i][j] = False
for i in range(n):
if palindrome[0][i]:
dp[i] = 0
else:
dp[i] = float('inf')
for j in range(i):
if palindrome[j + 1][i] and dp[j] + 1 < dp[i]:
dp[i] = dp[j] + 1
result = []
index = n - 1
while index >= 0:
for j in range(index + 1):
if palindrome[j][index] and (j == 0 or dp[j - 1] + 1 == dp[index]):
result.insert(0, s[j:index + 1])
index = j - 1
break
return result
# Example usage
sol = Solution()
print(sol.minCutPalindromes("aab")) # Output: ["aa", "b"]
print(sol.minCutPalindromes("racecarannakayak")) # Output: ["racecar", "anna", "kayak"]
print(sol.minCutPalindromes("abac")) # Output: ["a", "b", "a", "c"]
Complexity
- ⏰ Time complexity:
O(n^2)
for filling thedp
andpalindrome
tables. - 🧺 Space complexity:
O(n^2)
for storing thedp
andpalindrome
tables.
Method 2 -
Code
Java
Python
Complexity
- ⏰ Time complexity:
O(NNNXXXNNN)
- 🧺 Space complexity:
O(NNNXXX)