algoadvance

Leetcode 131. Palindrome Partitioning

Problem Statement

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

Example:

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

Clarifying Questions

1. Is the string s always non-empty?
   • Yes, in the context of this problem, assume the string s is always non-empty.
2. Can the string s consist of any characters other than lowercase or uppercase alphabets?
   • For the sake of simplicity, assume the string only contains lowercase English letters.
3. Is the order of the partitions in the output important?
   • No, the order of partitions in the output list is not important.

Strategy

The problem can be approached using a backtracking algorithm. Here’s the step-by-step strategy:

1. Backtracking Framework:
   • We will recursively explore all possible partitions of the string s.
   • For each prefix of the string, check if it is a palindrome.
   • If the prefix is a palindrome, recursively partition the remaining substring.
2. Palindrome Check:
   • A helper function isPalindrome will be used to check whether a given substring is a palindrome.
3. Base Case:
   • If we reach the end of the string, we add the current partition to the result list.
4. Recursive Case:
   • Iterate through the string and recursively partition the substring starting at the current index.

Code

#include <vector>
#include <string>
#include <iostream>

using namespace std;

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> result;
        vector<string> current;
        backtrack(result, current, s, 0);
        return result;
    }
    
private:
    void backtrack(vector<vector<string>>& result, vector<string>& current, const string& s, int start) {
        if (start == s.size()) {
            result.push_back(current);
            return;
        }
        
        for (int end = start; end < s.size(); ++end) {
            if (isPalindrome(s, start, end)) {
                current.push_back(s.substr(start, end - start + 1));
                backtrack(result, current, s, end + 1);
                current.pop_back();
            }
        }
    }
    
    bool isPalindrome(const string& s, int left, int right) {
        while (left < right) {
            if (s[left] != s[right]) return false;
            ++left;
            --right;
        }
        return true;
    }
};

int main() {
    Solution sol;
    string input = "aab";
    vector<vector<string>> result = sol.partition(input);

    for (const auto& partition : result) {
        for (const auto& str : partition) {
            cout << str << " ";
        }
        cout << endl;
    }

    return 0;
}

Time Complexity

• IsPalindrome Function: (O(n)) for each call, where (n) is the length of the palindrome being checked.
• Backtracking:
  • In the worst case, every substring needs to be checked for being a palindrome.
  • There are (2^(n-1)) possible ways to partition a string of length (n).

Thus, the time complexity can be approximated to (O(n \cdot 2^n)) due to the nested nature of the backtracking and palindrome check operations.

Space Complexity

• The space complexity is (O(n)) due to the recursion stack and the space needed for storing the temporary partitions in current.

This solution effectively balances both clarity and efficiency for the given problem constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?