最长回文字串,首先要明白子串和子序列的区别,子串是连续的,子序列不一定是连续的,而回文就是从左到右读,或者从右到左读都是一样的。
题目的要求是在一个字符串中找出最长的那个回文子串,比如:
s = “babad”
最长回文子串就是 “bab”, “aba” 也是一个有效答案。
而这道题我们应该怎么分析呢?
我们分析回文子串,发现它其实是关于中心对称的,
那我们就可以这样想了,是不是可以确定一个字符,将其作为中心,然后向两边延展,
如果该字符的左右两边字符相同,那就继续延展,如果不同,就记录下此时长度。
比如像这样,当以a为中心时,对比其左右两端,发现其相等,那就继续延展,而左边已经到达字符串头部,不能再继续延展,此时就要记录现在的长度。
这就是中心扩散算法,
但很快我们就会发现问题,如果仅凭判断某个字符左右两端的字符是否相等来决定扩展,你会发现下面这种情况会被抛弃,
而我们可以看的出来,该字符串的最长回文子串应该是 “babbab”,
没错,我们刚刚把中心看成是一个字符,却忽略了中心是可以为多个相同字符的,
所以我们要对将这种特殊性考虑进去,把这个看成第二种情况,
需要在延展判断之前先确定中心的字符,
这样子,当我们确定了中心字符后,就可以往两边扩展,
当不能继续扩展的时候就将当前的长度与以记录的最长回文子串长度进行比较,
更新最长的长度,并记录此时子串的起始位置
因为最后我们的结果是返回一个字符串,当我们知道子串的起始位置和长度之后,就可以使用 substring(index, index + len) 截取子串
中心扩散的代码就可以写出来了:
1 | public String longestPalindrome(String s) { |
中心扩散方法其实还有一种写法,
上面我们讨论了中心字符的两种情况,第一种是中心是单独的一个字符,第二种是中心有多个相等的字符,
如果将第二种情况分为中心有奇数个相等的字符和偶数个相等的字符。
现在我们就对这种情况进行讨论,但有奇数个时候,如果为 1,我们就取这个作为我们的中心,如果是大于 1 的奇数,我们取最中间那个,因为左右两端一定相等,而如果是偶数个,如果是2,我们就取这两个,如果是大于 2 的偶数,我们只取最中心的两个作为中心。
结合起来其实就是:
1 | //palindrome(s, left, right)为延展判断回文串的函数 |
完整代码就是:
1 | public String longestPalindrome(String s) { |
解决最长回文子串的方法除了有中心扩散方法,还有动态规划,动态规划是对暴力解法的优化。
回文子串,当去掉两头后,还是回文子串,所以,当我们要确定一个子串是否为回文子串时,就需要两个东西:
- 此时两端是否相等
- 去掉两端后是否还为回文子串
如果满足以上两个条件,此时的字串就是回文子串
这就是我们的状态。
状态就是此时 [i, j] 的子串是否为回文子串,
1 | 如果是:dp[i][j] = true |
而结合上面,我们的状态转移方程就可以推导出来了:
1 | dp[i][j] = dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j) |
还需要确定几个细节问题,
对于单独一个字符来说,肯定是回文子串,所以在初始化dp数组时,应该将
1
dp[i][i] = true
因为要去掉两端判断,当只有两个字符时,去掉后无法再进行判断,所以[i + 1, j - 1]的长度要大于等于2,即 j - 1 - (i + 1) > 1,即 j - i > 3
完整代码:
1 | public String longestPalindrome(String s) { |