Leetcode 131: Palindrome Partitioning

[
  ["aa","b"],
  ["a","a","b"]
]

Code

class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        res = []
        self.recur(0, s, [], res)
        return res

    def recur(self, cur_idx, s, splits, res):
        if cur_idx == len(s):
            res.append(list(splits))
            return

        for i in xrange(cur_idx + 1, len(s)+1):
            if self.isPalindrome(s[cur_idx:i]):
                splits.append(s[cur_idx:i])
                self.recur(i, s, splits, res)
                splits.pop()

    def isPalindrome(self, ss):
        return ss == ss[::-1]

Idea

You progressively try every split position in the string. Check whether substring between the last split position to current split position is palindrome. If so, recursively try the rest of split positions, with the current substring being added to splits.

Reference: https://discuss.leetcode.com/topic/10955/clean-c-backtracking-solution