python语法：分割回文串（2）

题目：

给定一个字符串 s ，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:

输入: "aab"
  ["aa","b"],
  ["a","a","b"]
]

解法：

思路如下，题目要求返回所有的可能方案，所以采用回溯算法。

循环查看当前字符串的每一个可切分位置位；判断若在当前位置切分，前半部分是否是回文串。若是，则将前半部分存入当前解，并递归分割后半部分。

例如输入字符串为示例：

|a 　|a　 |b　 |

0　１　２　３

好了用这个例子一步步开始写代码了：

1.检查某段字符串是否为回文串

def check(self,s):
		if len(s) ==0:
			return False
		else:
			start=0
			end = len(s) -1
			while start<=end:
				if s[start] != s[end]:
					return False
				else:
					start+=1
					end -=1
			return True

2.发现前半部分‘a’是回文串，将‘a’存入cur_res，将后半部分‘ab’用作递归。将cur_res加入的result，最终返回result

def partition_helper(self,s,cur_res,result):
		if len(s)==0:
			result.append(cur_res)
		for i in range(1,len(s)+1):
			if self.check(s[:i]):
				self.partition_helper(s[i:],cur_res + [s[:i]],result)

3.当输入字符串为空时，递归结束

	def partition(self,s):
		if len(s)==0:
			return []
		else:
			res=[]
			self.partition_helper(s,[],res)
		return res

总代码如下，测试一下，搞定：

class Solution(object): 
	def check(self,s):
		if len(s) ==0:
			return False
		else:
			start=0
			end = len(s) -1
			while start<=end:
				if s[start] != s[end]:
					return False
				else:
					start+=1
					end -=1
			return True
	def partition_helper(self,s,cur_res,result): 
		if len(s)==0:
			result.append(cur_res)
		for i in range(1,len(s)+1):
			if self.check(s[:i]):
				self.partition_helper(s[i:],cur_res + [s[:i]],result)
	def partition(self,s):
		if len(s)==0:
			return []
		else: