描述
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 (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
|
近期评论