回文字符串问题可以看做是一个划分链问题,这个和算法导论中介绍动态规划时的矩阵链乘法是一样的,找到一个最优的划分方案。很自然的想到动态规划来得到一个回文串的真值表,然后就是要列举出所有的情况,回溯法可以做到,自然而然的DP+BackTracking解决掉。

题目

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”] ]

代码

分析在摘要中都说了,这里注意一下DP时候的细节,就是先单独算两长度的,然后按照长度逐个求解,长串判断需要依赖短串的状态,这是DP的关键。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注