【题目描述】
Given a strings, partitionssuch that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
给定一个字符串s，将s分割成一些子串，使每个子串都是回文串。
【题目链接】
www.lintcode.com/en/problem/palindrome-partitioning/
【题目解析】
罗列所有可能，典型的DFS. 此题要求所有可能的回文子串，即需要找出所有可能的分割，使得分割后的子串都为回文。凭借高中的排列组合知识可知这可以用『隔板法』来解决，具体就是在字符串的每个间隙为一个隔板，对于长度为 n 的字符串，共有 n-1 个隔板可用，每个隔板位置可以选择放或者不放，总共有 O(2n?1)O(2^{n-1})O(2n?1) 种可能。由于需要满足『回文』条件，故实际上需要穷举的状态数小于 O(2n?1)O(2^{n-1})O(2n?1).
【参考答案】
作者：程风破浪会有时
链接：http://www.jianshu.com/p/b836554e93ed
來源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/31475320/viewspace-2142286/ ，如需转载，请注明出处，否则将追究法律责任。
