题目

131. 分割回文串
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例:

  1. 输入: "aab"
  2. 输出:
  3. [
  4.   ["aa","b"],
  5.   ["a","a","b"]
  6. ]

题解

朴素解法

这道题很明显用递归来做，首先从左边取一个回文子串，然后将剩下的右子串再次调用函数递归，得到右子串的分割方案，然后将左回文子串添加到所有分割方案中，即得到了当前串的一部分分割方案。
只需将左边的回文串全遍历一遍，然后将分割方案汇总，便是所有的分割方案。

  1. class Solution(object):
  2.     def IsOK(self,s):
  3.         for i in range(len(s)//2):
  4.             if s[i]!=s[-i-1]:
  5.                 return False
  6.         return True
  8.     def partition(self, s):
  9.         L=[]
  10.         for i in range(len(s)):
  11.             if self.IsOK(s[:i+1]):
  12.                 if len(s[i+1:])==0:
  13.                     L.append([s[:i+1]])
  14.                     break
  15.                 res_list=self.partition(s[i+1:])
  16.                 for sub_list in res_list:
  17.                     L.append([s[:i+1]]+sub_list)
  18.         return L

但是这种方法用时312 ms，只超过了9%的方案，因此可以继续优化。

优化

普通的递归最大的缺点就是重复情况太多，因此我们用一个字典储存已经得到的方案，这样下一次就不需要再计算一次：

  1. class Solution(object):
  2.     def __init__(self):
  3.         self.D=dict()
  5.     def IsOK(self,s):
  6.         for i in range(len(s)//2):
  7.             if s[i]!=s[-i-1]:
  8.                 return False
  9.         return True
  11.     def partition(self, s):
  12.         if s in self.D:
  13.             return self.D[s]
  14.         L=[]
  15.         for i in range(len(s)):
  16.             if self.IsOK(s[:i+1]):
  17.                 if len(s[i+1:])==0:
  18.                     L.append([s[:i+1]])
  19.                     break
  20.                 res_list=self.partition(s[i+1:])
  21.                 for sub_list in res_list:
  22.                     L.append([s[:i+1]]+sub_list)
  23.         self.D[s]=L
  24.         return L

这次执行用时132 ms, 在所有 Python 提交中击败了86.82%的用户，可以说效果很好了。

看了其他题解之后，发现判断是否为回文串时，也会出现重复情况，因此对于该函数，我们也进行状态记录：

  1. class Solution(object):
  2.     def __init__(self):
  3.         self.D=dict()
  4.         self.S=dict()
  6.     def IsOK(self,s):
  7.         if len(s)<=1:
  8.             return True
  9.         elif s[0]!=s[-1]:
  10.             return False
  11.         elif s in self.D:
  12.             return self.D[s]
  13.         else:
  14.             self.D[s]=self.IsOK(s[1:-1])
  15.             return self.D[s]
  17.     def partition(self, s):
  18.         if s in self.D:
  19.             return self.D[s]
  20.         L=[]
  21.         for i in range(len(s)):
  22.             if self.IsOK(s[:i+1]):
  23.                 if len(s[i+1:])==0:
  24.                     L.append([s[:i+1]])
  25.                     break
  26.                 res_list=self.partition(s[i+1:])
  27.                 for sub_list in res_list:
  28.                     L.append([s[:i+1]]+sub_list)
  29.         self.D[s]=L
  30.         return L

执行用时：124 ms, 在所有 Python 提交中击败了88.47%的用户。
优化不是很明显，聊胜于无吧。