Palindrome Partitioning

'''
Bottom up DP:
in most cases some subproblems are never used
dp[i] = lists of all valid partitions of suffixes starting from i
dp[i] = palindromes starting from i of len p + partitions in  dp[i+p] for all 1<=p<=N-i
Base case dp[N] = [[]]
Also palindrome prefixes of s[i+1:] can be obtained from palindrome prefixes of s[i:]
'''
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        s += '/'
        palindromes = []
        partitions = {n: [[]]}
        for i in range(n-1, -1, -1):
            temp = [s[i]]
            for p in palindromes:
                pos = i+len(p)+1
                if s[i] == s[pos]:
                    temp.append(s[i:pos+1])

            partitions[i] = []
            for p in temp:
                pos = i+len(p)
                for q in partitions[pos]:
                    partitions[i].append([p] + q)
            palindromes = [''] + temp

        return partitions[0]

'''DP for palindrome check + bactracking:
dp[l][r] = isPalindrome(s[l...r])
dp[l][r] = True. for r == l
         = s[l] == s[r]. for r == l+1
         = dp[l+1][r-1] && (s[l] == s[r]) otherwise
'''
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        N = len(s)
        s += '/'
        dp = [[False]*(N+1) for _ in range(N)]
        for L in range(N-1, -1, -1):
            dp[L][L] = True
            dp[L][L+1] = (s[L] == s[L+1])
            for R in range(L+2, N):
                dp[L][R] = (s[L] == s[R]) and dp[L+1][R-1]
        res = []

        def backtrack(curr, partition):
            if curr == N:
                res.append(partition[:])

            for right in range(curr, N):
                if dp[curr][right]:
                    partition.append(s[curr:right+1])
                    backtrack(right+1, partition)
                    partition.pop()
        backtrack(0, [])

        return res

'''
Bactracking with memoized palindrome check
'''
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        N = len(s)
        res = []

        @cache
        def isPal(s, curr, right):
            while curr<=right and s[curr] == s[right]:
                curr += 1
                right -= 1
            return curr > right


        def backtrack(curr, partition):
            if curr == N:
                res.append(partition[:])

            for right in range(curr, N):
                if isPal(s, curr, right):
                    partition.append(s[curr:right+1])
                    backtrack(right+1, partition)
                    partition.pop()
        backtrack(0, [])

        return res