131. Palindrome Partitioning

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 <= 16
• s contains only lowercase English letters.

Approach 01:

#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> result;
        solve(s, 0, {}, result);
        return result;
    }

private:
    void solve(const string& s, int start, vector<string>&& path,
             vector<vector<string>>& result) {
        if (start == s.length()) {
            result.push_back(path);
            return;
        }

        for (int i = start; i < s.length(); ++i)
            if (isPalindrome(s, start, i)) {
                path.push_back(s.substr(start, i - start + 1));
                solve(s, i + 1, move(path), result);
                path.pop_back();
            }
    }

    bool isPalindrome(const string& s, int l, int r) {
        while (l < r)
            if (s[l++] != s[r--])
                return false;
        return true;
    }
};

from typing import *

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        result = []

        def isPalindrome(s: str) -> bool:
            return s == s[::-1]

        def solve(s: str, j: int, path: List[str], result: List[List[str]]) -> None:
            if j == len(s):
                result.append(path)
                return

            for i in range(j, len(s)):
                if isPalindrome(s[j : i + 1]):
                    solve(s, i + 1, path + [s[j : i + 1]], result)

        solve(s, 0, [], result)
        return result

Time Complexity

• Recursive Partitioning:

  The function partition recursively partitions the string s into palindromic substrings. The isPalindrome function is called to check each substring’s palindromic property.

• Recursive Calls:

  In the worst case, the algorithm explores all possible partitions of the string. The number of partitions can grow exponentially with the input size, considering all possible divisions of the string.

• Overall Time Complexity:

  The overall time complexity is \( O(n \cdot 2^n) \), where \( n \) is the length of the input string s. This complexity arises due to the exponential number of possible partitions and the linear time check for each partition.

Space Complexity

• Recursive Stack Space:

  The space complexity is determined by the maximum depth of the recursion stack, which is equal to the maximum number of recursive calls made.

• Path Storage:

  Each valid partition (path) is stored temporarily in the path vector, which contributes to space usage.

• Overall Space Complexity:

  The overall space complexity is \( O(n \cdot 2^n) \), similar to the time complexity. This is dominated by the space required for storing all possible partitions and the recursion stack space.