C++: Palindrome Partitioning

Thought Process

The problem requires partitioning a string into all possible palindromic substrings. We use backtracking to explore all valid partitions. For each position in the string, we check if the substring from the current position to a chosen endpoint is a palindrome. If it is, we add it to the current partition and recursively explore further. Once we reach the end of the string, we add the valid partition to the result. This ensures we explore all possible ways to partition the string into palindromic substrings. 

class Solution {
public:
    bool isPalindrome(string str, int start, int end){

        while(start<end){

            if(str[start]!=str[end])
                return false;
            
            start++;
            end--;
        }
        return true;
    }
    void backTrack(vector<vector<string>> &ans, vector<string> &tmp, string str, int start){

        if(start==str.size()){
            ans.push_back(tmp);
            return;
        }

        for(int i=start;i<str.size();i++){

            if(isPalindrome(str,start,i)){

                int length = (i-start+1); // Length of substring we want to construcut.
                tmp.push_back(str.substr(start,length)); // Push the substring into the tmp
                backTrack(ans,tmp,str,i+1);
                tmp.pop_back(); // Remove the added substring and try finding other solutions.
            }
        }
            
    }
    vector<vector<string>> partition(string str) {
        
        vector<vector<string>> ans;
        vector<string> tmp;

        backTrack(ans,tmp,str,0);
        return ans;
    }
};

Code Complexity

Time Complexity: O(n * 2^n)

The algorithm explores all possible partitions of the string, resulting in exponential time complexity. Each partition check takes O(n) time.

Space Complexity: O(n)

The algorithm uses recursion, which consumes stack space proportional to the length of the string.

Code copied!