当前位置： 移动技术网 > IT编程>开发语言>C/C++ > LeetCode Palindrome Partitioning

LeetCode Palindrome Partitioning

2019年01月06日  | 移动技术网IT编程  | 我要评论

七十二层奇楼常驻嘉宾,星河步兵,德国化工厂爆炸

leetcode解题之palindrome partitioning

原题

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

注意点：

无

例子:

输入: s = “aab”

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

解题思路

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

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

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网