Palindrome Partitioning
Problem Description
Question
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
Example 1:
Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]
Example 2:
Input: s = "a"
Output: [["a"]]
Constraints:
1 <= s.length <= 16scontains only lowercase English letters.
Solve it on LeetCode
Approaches
1. Backtracking
Intuition:
The core idea is to use backtracking to generate all possible partitioning of the string, and for each partitioning, check if the substrings are palindromes. Backtracking is well-suited for this type of problem because we can recursively try each possible partition and backtrack if it does not lead to a solution.
- Start from the beginning of the string and for each character at position
i, check if the substring from the start toiis a palindrome. - If it is a palindrome, recursively partition the rest of the string from
i+1. - If a partitioning of the entire string is found, add it to the result list.
Code:
Complexity Analysis
- Time Complexity: O(n * 2^n), where n is the length of the string. This complexity is due to the fact that each character might either start its own substring or extend a previous one, leading to exponential possibilities.
- Space Complexity: O(n), where n is the depth of the recursion. The space is used by the recursive call stack.
2. Dynamic Programming + Backtracking
Intuition:
We can optimize the palindrome checking part by using dynamic programming (DP). Using a 2D DP array, we can store the palindrome status of substrings to avoid recomputing this information repeatedly.
- Precompute a 2D array
dpwheredp[i][j]is true if the substrings[i:j+1]is a palindrome. - Use this DP table in the backtracking process to quickly check if a substring is a palindrome.
Code:
Complexity Analysis
- Time Complexity: O(n^2 * 2^n), where n is the length of the string. The DP precomputation is O(n^2), and the backtracking process remains exponential.
- Space Complexity: O(n^2) for the DP table plus O(n) for the recursion stack.