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"]
]
Keys: 1. 一般列出所有组合，可能性，etc 的题目都可以用DFS.
2. L8. 对于Class Solution中的全局变量x，可以用Solution.x
class Solution(object):
def partition(self, s):
"""
:type s: str
:rtype: List[List[str]]
"""
Solution.res = []
self.DFS(s, [])
return Solution.res def DFS(self, s, stringlist):
if len(s) == 0:
Solution.res.append(stringlist)
# 如果一开始的substring是palin，把他存到stringlist中
for i in range(1, len(s)+1):
if self.isPalin(s[:i]):
self.DFS(s[i:], stringlist + [s[:i]]) def isPalin(self, s):
for i in range(len(s)):
if s[i] != s[len(s)-1-i]:
return False
return True