Below is my DP solution in python, ~ 300 ms. O(n) to traverse the DP array. For each subproblem, traverse backwards to find all palindromes, O(n). Checking palindrome takes another O(n). So it seems that my solution is O(n^3). I think the worst case is a string like "aaaaaaaaaaaaaaaaaa ... a".

Not sure how to reduce to O(n^2). But I like it anyway, because it is consice :)

EDIT: Actually it is worse than O(n^3), because each step needs to loop through the previous subsolution and do list concatenation on each of them. Sounds like at least O(n^5) ...

wonder why it can pass the TLE tests

```
class Solution:
# @param s, a string
# @return a list of lists of string
def partition(self, S):
def isPalindrome(i, j):
while i < j:
if S[i] != S[j]: return False
i += 1
j -= 1
return True
# DP[i] caches all partitions of s[:i]
# each partition is a list of strings
DP = [[[]]]
# topological order: from left to right
for i in xrange(len(S)):
ptn = []
# check all possible palindormes ending at s[i]
for j in reversed(range(i+1)):
if isPalindrome(j, i):
ptn.extend(q + [S[j:i+1]] for q in DP[j])
DP.append(ptn)
return DP[-1]
```