```
class Solution:
# @param s, a string
# @return a list of lists of string
def partition(self, s):
graph = collections.defaultdict(set)
n = len(s)
for j in range(n):
for i in range(j, n):
if s[j:i+1] == s[j:i+1][::-1]:
graph[j].add(i+1)
stack, res = [[0]], []
while stack:
route = stack.pop()
node = route[-1]
if node == n:
res.append([s[j:i] for (j, i) in zip(route[:-1], route[1:])])
for neighbor in graph[node]:
stack.append(route+[neighbor])
return res
```