Leetcode解题-Palindrome Partitioning

发表于   |   分类于   |  

描述

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

Return all possible palindrome partitioning of s.

For example, given s = “aab”,
Return

[
[“aa”,”b”],
[“a”,”a”,”b”]
]

分析

一个长度为n的字符串有n - 1个空隙，每个空隙可以选择切还是不切，所以共有2 ^ (n - 1)种划分。使用回溯法，时间复杂度O(n*2^n)，空间O(n)。

代码

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution(object):
    def isPalindrome(self, s, start, end):
        while start <= end:
            if s[start] != s[end]:
                return False
            start += 1
            end -= 1
        return True

    def dfs(self, s, path, rs, start):
        n = len(s)
        if start == n:
            rs.append(path[:])
            return

        for i in xrange(start, n):
            if self.isPalindrome(s, start, i):
                path.append(s[start: i + 1])
                self.dfs(s, path, rs, i + 1)
                path.pop()

    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        n = len(s)
        if n == 0:
            return [[]]
        path = []
        rs = []
        self.dfs(s, path, rs, 0)
        return rs

热评文章