Medium

Palindrome Partitioning

084

Return all palindrome partitions of s, with each partition joined by | and sorted lexicographically.

EXAMPLES

Example 1

Input
{
  "s": "aab"
}

Output
[
  "a|a|b",
  "aa|b"
]

FUNCTION SHAPE

s: string→stringArray

SOLUTION NOTE

Same idea. Our choices are substrings from i to j instead of single instances of j now. We try all substrings that start at index i, and if it's palindromic we backtrack.

Reveal reference solution +

pythonREFERENCE

def partition(self, s: str) -> List[List[str]]:
    res = []
    curr = []
    n = len(s)

    def backtrack(i):
        if i == n:
            res.append(curr.copy())
            return

        for j in range(i, n):
            segment = s[i:j+1]

            if segment == segment[::-1]:
                curr.append(segment)
                backtrack(j+1)
                curr.pop()

    backtrack(0)
    return res

TimeO(n*2^n)

SpaceO(n*2^n)

Open on LeetCode ↗