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"]
    ]