Palindrome Partition

Problem

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

---

Idea

首先对字符串的所有子串判断是否是回文，设f[i][j] = true表示以i为起点，长度为j的子串是回文,等于false表示不是回文，那么求f[i][j]的动态规划方程如下：

当j = 1，f[i][j] = true;
当j = 2，f[i][j] = (s[i]==s[i+1]),其中s是输入字符串
当j > 2, f[i][j] = f[i+1][j-2] && (s[i] == s[i+j-1])（即判断s[m..n]是否是回文时：只要s[m+1...n-1]是回文并且s[m] = s[n]，那么它就是回文，否则不是回文）

---

Solution

---