forked from CodingVault/LeetCodeInPython
-
Notifications
You must be signed in to change notification settings - Fork 0
/
palindrome_partition.py
78 lines (60 loc) · 1.8 KB
/
palindrome_partition.py
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#!/usr/bin/env python
# encoding: utf-8
"""
palindrome_partition.py
Created by Shengwei on 2014-07-02.
"""
# https://oj.leetcode.com/problems/palindrome-partitioning/
# tags: medium, string, dp, palindrome, dfs
"""
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"]
]
"""
# time complexity:
# to solve n chars, it needs to call is_palindrome several times.
# f(n) = 1 + f(n-1) + 1 + f(n-2) + ... + 1 + f(1) + 1
# = n + f(n-1) + f(n-2) + ... + f(1)
# = n + n - 1 + f(n-2) + f(n-3) + ... + f(1) # no 2f(n-2) due to cache
# = O(n^2) times of calls to is_palindrome -- for O(n^2) substrings
# possibly better solution, pre-compute is_palindrome; maybe no gain
# https://oj.leetcode.com/discuss/5976/any-way-to-reduce-the-runtime
def is_palindrome(s):
if len(s) < 2:
return True
left, right = 0, -1
while left - right < len(s):
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
cache = {}
def recursive_par(s):
if s in cache:
return cache[s]
if len(s) == 1:
return [[s]]
res = []
for i in xrange(len(s)):
sub, remainder = s[:i+1], s[i+1:]
if is_palindrome(sub):
if remainder == '':
res.append([sub])
continue
pars = recursive_par(remainder)
if pars:
cache[remainder] = pars
for par in pars:
res.append([sub] + par)
return res
class Solution:
# @param s, a string
# @return a list of lists of string
def partition(self, s):
return recursive_par(s)