LeetCode Palindrome Partitioning

leetcode解题之palindrome partitioning

---

原题

将一个字符串分割成若干个子字符串，使得子字符串都是回文字符串，要求列出所有的分割方案。

注意点：

无

例子:

输入: s = “aab”

输出: result = [[“a”, “a”, “b”], [“aa”, “b”]]

解题思路

采用了最简单的递归方法，将一个字符串分为前后两部分，如果第一部分是一个回文字符串，则对第二部分再次分割，不断递归，直到递归的终止条件——字符串为空为止；如果第一部分不是一个回文字符串，则尝试下一种分割方法。

源码">ac源码

class solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: list[list[str]]
        """
        if not s:
            return [[]]
        result = []
        for i in range(len(s)):
            if self.ispalindrome(s[:i + 1]):
                for r in self.partition(s[i + 1:]):
                    result.append([s[:i + 1]] + r)
        return result

    def ispalindrome(self, s):
        return s == s[::-1]


if __name__ == "__main__":
    assert solution().partition("aab") == [
        ["a", "a", "b"],
        ["aa", "b"]
    ]