Palindrome Partitioning
Challenge Given a String S return all palindrome partitions. Example 1: Input: s = "abc" Output: [["a","b","c"] Example 2: Input: s = "abb" Output: [["a","bb"],["a", "b", "b"]] Solution Get all subset of the string. Check if this subset is only composed of palindromes If so add it to the result class Solution: def check_palindrome(self, s): stack = [] for e in list(s): stack.insert(0, e) for e in s: i = stack.pop(0) if i != e: return False return True def get_all_subsets(self, start, s, arr): if arr and not 0 in arr: self._set.add(tuple(arr[:])) for i in range(start, len(s)): arr.append(i) self.get_all_subsets(i+1, s, arr) arr.pop() return def cutter(self, s, cuts): res = [] for cut in cuts: cut = list(cut) cut = [0] + cut + [len(s)] tmp = [] for i, e in enumerate(cut): if i > 0: tmp.append(s[cut[i-1]:cut[i]]) ct = 0 for t in tmp: if self.check_palindrome(t): ct +=1 if ct == len(tmp): res.append(tmp) if self.check_palindrome(s): res.append([s]) return res def partition(self, s: str) -> List[List[str]]: if not s: return if len(s) == 1: return [s] self._set = set() self.get_all_subsets(0, s, []) return self.cutter(s, self._set) Time complexity Space Complexity O(2^n) O(n)