LC 0131 [M] Palindrome Partitioning - ALawliet/algorithms GitHub Wiki

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        res = []
        part = []
        
        def isPali(l, r):
            while l < r:
                if s[l] != s[r]:
                    return False
                l += 1 ; r -= 1
            return True

        def dfs(i, part):
            if i >= len(s):
                res.append(part)
            else:
                for j in range(i, len(s)):
                    if isPali(i, j):
                        dfs(j + 1, part + [s[i:j+1]])
        dfs(0, [])
        return res