Q78: Palindrome Partitioning. - DSA Patterns (Multi-Lang)

In Simple Words: At index $i$, test all substrings s[i...j]. If s[i...j] is a palindrome, add it to currentPartition and recursively solve suffix j + 1.

Time: $O(N \cdot 2^N)$ | Space: $O(N)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

def partition(s: str) -> list[list[str]]:
    res = []
    part = []
    def is_pali(sub, l, r):
        while l < r:
            if sub[l] != sub[r]: return False
            l += 1; r -= 1
        return True

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