SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

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

Intuition

To solve this problem, we need to generate all possible partitions of the string and then check if each partition is a palindrome. Using a recursive approach, we can explore every possible partitioning. We will use dynamic programming to store previously computed results and avoid redundant calculations.

Approach

1. Helper Function for Palindrome Check:

   • Define a helper function isPalin that checks if a substring s[left:right+1] is a palindrome.
   • Use a while loop to compare characters from both ends of the substring.

2. Dynamic Programming Table Initialization:

   • Create a list of lists dp where dp[i] stores all the palindrome partitions from the start of the string to index i.

3. Building the DP Table:

   • Iterate through the string with a nested loop:
     • The outer loop (i) iterates over each end index of the substring.
     • The inner loop (k) iterates backward from the end index to find all starting indices of substrings ending at i.
     • If a palindrome substring is found, add it to the current partition.
     • If the palindrome starts from the beginning (k == 0), create a new partition.
     • Otherwise, extend existing partitions ending at k-1 by adding the current palindrome substring.

4. Return the Result:

   • The result is stored in dp[n-1], where n is the length of the input string.

Complexity

Time Complexity:

O(n^2 * 2^n), where n is the length of the input string. This complexity arises because there are 2^n possible partitions, and for each partition, we check the palindrome property, which takes O(n) time in the worst case.

Space Complexity:

O(n * 2^n), where n is the length of the input string. This space is used to store all possible partitions in the dynamic programming table.

Code

C++

class Solution {
public:
    vector<vector<string>> partition(string s) {
        int n = s.length();
        vector<vector<vector<string>>> dp(n);

        for (int i = 0; i < n; ++i) {
            for (int k = i; k >= 0; --k) {
                if (isPalin(s, k, i)) {
                    string str = s.substr(k, i - k + 1);
                    if (k == 0) {
                        dp[i].push_back({str});
                    } else {
                        for (const auto& prevPalin : dp[k - 1]) {
                            vector<string> newPartition = prevPalin;
                            newPartition.push_back(str);
                            dp[i].push_back(newPartition);
                        }
                    }
                }
            }
        }
        return dp[n - 1];
    }
private:
    bool isPalin(const string& s, int left, int right) {
        while (left < right) {
            if (s[left] != s[right]) {
                return false;
            }
            ++left;
            --right;
        }
        return true;
    }
};

Python

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        dp = [[] for _ in range(n)]
        
        def isPalin(left: int, right: int) -> bool:
            while left < right:
                if s[left] != s[right]:
                    return False
                left += 1
                right -= 1
            return True
        
        for i in range(n):
            for k in range(i, -1, -1):
                if isPalin(k, i):
                    str_part = s[k:i + 1]
                    if k == 0:
                        dp[i].append([str_part])
                    else:
                        for prev in dp[k - 1]:
                            dp[i].append(prev + [str_part])
        
        return dp[-1]

Java

class Solution {
    public List<List<String>> partition(String s) {
        int n = s.length();
        List<List<List<String>>> dp = new ArrayList<>(n);

        for (int i = 0; i < n; i++) {
            dp.add(new ArrayList<>());
            for (int k = i; k >= 0; k--) {
                if (isPalin(s, k, i)) {
                    String str = s.substring(k, i + 1);
                    if (k == 0) {
                        List<String> newPartition = new ArrayList<>();
                        newPartition.add(str);
                        dp.get(i).add(newPartition);
                    } else {
                        for (List<String> prevPalin : dp.get(k - 1)) {
                            List<String> newPartition = new ArrayList<>(prevPalin);
                            newPartition.add(str);
                            dp.get(i).add(newPartition);
                        }
                    }
                }
            }
        }
        return dp.get(n - 1);
    }
    private boolean isPalin(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

JavaScript

var partition = function (s) {
    function isPalin(left, right) {
        while (left < right) {
            if (s[left] !== s[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
    function getStr(left, right) {
        let str = '';
        for (let i = left; i <= right; i++) {
            str += s[i];
        }
        return str;
    }
    const dp = [];
    for (let i = 0; i < s.length; i++) {
        dp[i] = [];
        for (let k = i; k >= 0; k--) {
            if (isPalin(k, i)) {
                const str = getStr(k, i);
                if (k === 0) {
                    dp[i].push([str]);
                } else {
                    const arr = dp[k - 1] || [];
                    for (const prevPalin of arr) {
                        dp[i].push([...prevPalin, str])
                    }
                }
            }
        }
    }
    return dp[dp.length - 1];
};