👨‍💻 738LeetCode

Palindrome Partitioning

Question

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example

Input: "aab"
Output:
[
  ["aa","b"],
  ["a","a","b"]
]

Solution

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        def dfs(ptr, temp, ret):
            if ptr == len(s):  # All the way till end
                ret.append(temp.copy())
                return
            for i in range(ptr + 1, len(s) + 1):
                curr = s[ptr:i]
                if curr == curr[::-1]:
                    temp.append(curr)  # Have a try
                    dfs(i, temp, ret)  # Trying it...
                    temp.pop()  # You are done. Bye


        ret = []
        dfs(0, [], ret)
        return ret