最长回文串
字符串abcbada最长的回文串为abcba,最长回文串保证首尾字符相同,并且去除首尾后的子串也是回文串,如bcb。
根据这个规律,ab就不是回文串因为首尾不同。abcbada也不是回文串,因为即使首尾相同,其子串bcbad不是回文串,所以abcbada也不是回文串。
动态规划
可以通过动态规划解决字符串的最大回文串的长度问题,其根本思路是依次列举出长度为1~n的回文串,最后返回最大长度n即可。
动态规划的思路在于找出推导公式:
1 首尾元素不同,则不是回文串。
2 首尾元素相同,且去除首尾元素后得子串仍是回文串,则该串为回文串。
假设一个字符串str,我们将上述公式写成伪代码
1 | 1 str[begin] != str[end] 则str不是回文串 |
我们用二维数组dp[i][j]表示下标从i到j的字符串是否为回文串,如果是回文串则dp[i][j] == 1,否则dp[i][j] == 0
所以一个回文串应该满足如下条件
1 | dp[i+1][j-1] ==1 && str[i] == str[j] |
长度为1时,从i到i的字符串默认为回文串,dp[i][i] = 1
长度为2时,从i到i+1的字符串,判断str[i]==str[i+1] –> dp[i][i+1]=1
长度为3时,从i到i+2的字符串, 判断str[i] == str[i+2] && dp[i+1][i+1] ==1 -> dp[i][i+2] = 1
长度为4时,从i到i+3的字符串,判断str[i] == str[i+3] && dp[i+1][i+2] ==1 -> dp[i][i+3] = 1
…..
推导出dp的规律后开始写代码,将所有可能dp计算出来即可
1 | int max_palindrome(string str, string &palindstr) |
依次从长度3计算到字符串长度,最后更新的maxpalind为最大长度,回文串可能不止一个,这里返回最后一个。
在main函数中测试
1 | int main(){ |
程序输出
1 | Dynamic programming .... |
中心扩展法
用中心扩展法同样可以解决字符串回文问题,选在每个元素,将其设置为中心,如果满足回文串,则依次向左向右扩充,直到到达边界或者不满足回文串条件为止。
如下图
依次从索引为0的节点为中心,直到索引为4的节点,当以某个节点为中心时,判断他的左边节点和右边节点是否相等,如果相等则左节点向左,右节点向右,直到遇到左右节点不相等或者左右节点为边界节点结束。
举例:
当我们找到索引为2的节点c,判断他的左节点为b,右节点也为b,则左节点左移此时指向a,右节点右移指向a,此时左右节点已到达边界,就找到了最大的回文串abcba。
上述思路有一个问题就是面对如下情况,找到的最大回文串是不正确的。
按照上述办法无法找到最大回文串,而此回文串是存在的为abccba, 问题出在偶数节点对称的情况下,我们以索引为2的节点为中心,左节点为b,右节点为c无法找到回文串。解决的方案是将索引2设为左节点,索引3设为右节点就可以找到回文串。
所以扩展的方案修改为上述两种算法的并集
1 以单节点为中心,判断左右节点对称
2 以双节点为中心,判断左右节点对称
先实现根据左右节点相等,则左节点左移,右节点右移的逻辑
1 | int cal_maxlen(string str, int left, int right) |
上述代码根据左右节点差值-1计算出回文串长度。
接下来实现以节点为中心遍历展开的逻辑
1 | int center_expend(string str, string &palindstr) |
接下来在主函数中做测试
1 | int main(){ |
程序输出
1 | Center expend .... |
总结
解决字符串回文的算法还有马拉车算法,就是优先通过遍历在每个字符前后插入’#’,再执行中心扩展算法达到o(n)复杂度。这里不做赘述,个人认为善于通过动态规划和中心扩展算法解决回文问题即可。