grid47 Exploring patterns and algorithms
Oct 24, 2024
6 min read
Solution to LeetCode 131: Palindrome Partitioning Problem
You are given a string s. Partition the string into all possible substrings such that each substring is a palindrome.
Problem
Approach
Steps
Complexity
Input: The input is a string s of lowercase English letters.
Example: 'aab'
Constraints:
• 1 <= s.length <= 16
• s contains only lowercase English letters.
Output: The output is a list of all possible palindromic partitions of the input string.
Example: [['a', 'a', 'b'], ['aa', 'b']]
Constraints:
• The output will be a list of lists, where each list contains palindromic substrings.
Goal: The goal is to find all partitions of the string such that each substring is a palindrome.
Steps:
• 1. Perform a backtracking approach to explore all partitions of the string.
• 2. For each substring, check if it is a palindrome.
• 3. If it is a palindrome, add it to the current partition and proceed to partition the remaining part of the string.
• 4. If we reach the end of the string, add the partition to the result.
Goal: The string s will contain only lowercase English letters.
Steps:
• 1 <= s.length <= 16
• s contains only lowercase English letters.
Assumptions:
• The string s is non-empty and only contains lowercase letters.
• Input: 'aab'
• Explanation: The string can be partitioned into ['a', 'a', 'b'] or ['aa', 'b'], as both are palindromes.
• Input: 'a'
• Explanation: Since the string is just a single character, it is inherently a palindrome, and the only valid partition is ['a'].
Approach: We can use a backtracking approach to explore all possible partitions of the string, checking if each substring is a palindrome.
Observations:
• We need to check if substrings are palindromes.
• We will explore all possible partitions of the string.
• A backtracking approach works well because we can build the solution incrementally and backtrack when a non-palindromic substring is found.
Steps:
• 1. Create a helper function to check if a substring is a palindrome.
• 2. Use a recursive function with backtracking to explore all substrings of the string.
• 3. At each step, add palindromic substrings to the current partition and move forward.
• 4. Once a complete partition is found, add it to the result.
Empty Inputs:
• If the input string is empty, return an empty list.
Large Inputs:
• The algorithm should be able to handle the maximum string length of 16.
Special Values:
• If the string consists of a single character, the result should just be that character in a list.
Constraints:
• The string will contain only lowercase English letters.
vector<vector<string>> partition(string s) {
vector<vector<string>> ans;
vector<string> tmp;
bt(ans, tmp, s, 0);
return ans;
}
voidbt(vector<vector<string>>&ans, vector<string>&tmp, string s, int idx) {
if(idx == s.size()) {
ans.push_back(tmp);
return;
}
for(int i = idx; i < s.size(); i++) {
if(isPal(s, idx, i)) {
tmp.push_back(s.substr(idx, i - idx +1));
bt(ans, tmp, s, i +1);
tmp.pop_back();
}
}
}
boolisPal(string s, int i, int j) {
while(i <= j) {
if(s[i] != s[j])
returnfalse;
i++, j--;
}
returntrue;
}
1 : Function Declaration
vector<vector<string>> partition(string s) {
Define the `partition` function, which takes a string `s` and returns all possible palindrome partitions of the string.
2 : Variable Declaration
vector<vector<string>> ans;
Declare a 2D vector `ans` to store the resulting palindrome partitions.
3 : Variable Declaration
vector<string> tmp;
Declare a temporary vector `tmp` to store the current palindrome partition while exploring.
4 : Backtracking Call
bt(ans, tmp, s, 0);
Call the backtracking function `bt` to explore all possible partitions of the string starting from index 0.
5 : Return Statement
return ans;
Return the resulting 2D vector `ans` containing all valid palindrome partitions.
6 : Backtracking Function Declaration
voidbt(vector<vector<string>>&ans, vector<string>&tmp, string s, int idx) {
Define the `bt` function that performs backtracking to explore all possible palindrome partitions.
7 : Base Case Check
if(idx == s.size()) {
Check if the current index has reached the end of the string, indicating a valid partition.
8 : Push Partition
ans.push_back(tmp);
Add the current palindrome partition stored in `tmp` to the result vector `ans`.
9 : Return Statement
return;
Return from the function since we have found a valid partition.
10 : Loop Through Substrings
for(int i = idx; i < s.size(); i++) {
Loop through all possible substring endings starting from the current index `idx`.
11 : Palindrome Check
if(isPal(s, idx, i)) {
Check if the current substring from `idx` to `i` is a palindrome using the `isPal` function.
12 : Add Substring to Partition
tmp.push_back(s.substr(idx, i - idx +1));
If the substring is a palindrome, add it to the temporary partition vector `tmp`.
13 : Recursive Call
bt(ans, tmp, s, i +1);
Recursively call the backtracking function `bt` to explore further partitions starting from the next index `i + 1`.
14 : Remove Last Substring
tmp.pop_back();
Remove the last added substring from the temporary partition to explore other possible partitions.
15 : End Backtracking Function
}
End of the backtracking function `bt`.
16 : Palindrome Check Function Declaration
boolisPal(string s, int i, int j) {
Define the `isPal` function to check if a substring of `s` from index `i` to `j` is a palindrome.
17 : Loop for Palindrome Check
while(i <= j) {
Use a loop to compare characters at both ends of the substring, moving towards the center.
18 : Character Comparison
if(s[i] != s[j])
If characters at the current positions `i` and `j` don't match, return `false` since the substring is not a palindrome.
19 : Return False
returnfalse;
Return `false` if the substring is not a palindrome.
20 : Move Pointers
i++, j--;
Move the pointers `i` and `j` towards the center of the substring.
21 : Return True
returntrue;
Return `true` if the entire substring is a palindrome.
Best Case: O(n^2), where n is the length of the string. In the best case, the string has no valid partitions and only the single character partitions are considered.
Average Case: O(2^n), since there are potentially 2^n ways to partition the string.
Worst Case: O(n^2 * 2^n), where n is the length of the string, because we check each substring for being a palindrome for each partition.
Description: The time complexity arises from the recursive exploration of all partitions and palindrome checks.
Best Case: O(n), when only a few recursive calls are made.
Worst Case: O(n), due to the recursive call stack in the backtracking approach.
Description: The space complexity is dominated by the recursive stack and the space used to store the palindromic substrings.
