1. 问题描述
回文串（palindromic string）是指这个字符串无论从左读还是从右读，所读的顺序是一样的；简而言之，回文串是左右对称的。所谓最长回文子串问题，是指对于一个给定的母串
abcdedcb
从所有的为回文串的子串a, ded, cdedc, bcdecdb中；找出最长的那一个bcdecdb。但是该如何判断子串是否回文然后找出最长者呢？正好Leetcode也有一个5. longest-palindromic-substring问题，可以用来做代码测试。
2. 求解
2016.12.28更新
将原来的C代码替换为Go 1.7，修复了评论中所指出的动态规划bug。
穷举法
最容易想到的是穷举法，穷举所有子串，找出是回文串的子串，统计出最长的那一个。
// check whether a string is palindromic
func isPalindromic(s string) bool {
mid := len(s) / 2
last := len(s) - 1
for i := 0; i < mid; i++ {
if s[i] != s[last - i] {
return false
}
}
return true
}
// longest palindromic substring
func longestPalindrome(s string) string {
last := len(s) - 1
longest := string(s[0])
for i := 0; i < last; i++ {
for j := i + 1; j <= last; j++ {
if isPalindromic(s[i:j + 1]) && j + 1 - i > len(longest) {
longest = s[i:j+1]
}
}
}
return longest
}
- 时间复杂度：判断是否为回文串的复杂度为(O(n))，
longestPalindrome有双层for循环，因此总的复杂度为为(O(n^3))。 - 空间复杂度：(O(1))。
动态规划
穷举法的时间复杂度过高，接下来我们用DP进行优化。对于母串s，我们用(c[i, j] = 1)表示子串s[i..j]为回文子串，那么就有递推式
上述递推式的含义：当(s[i] = s[j])时，如果s[i+1..j-1]是回文子串，则s[i..j]也是回文子串；如果s[i+1..j-1]不是回文子串（或(s[i]
e s[j])），则s[i..j]也不是。
特别地，对于这样的字符串——只包含单个字符、或者两个字符重复，其均为回文串：
- c[i,i] = 1
- c[i,i+1] = 1 if s[i] == s[i+1]
func longestPalindrome(s string) string {
length := len(s)
// longest palindromic substring
longest := string(s[0])
// 2-D array initialization
c := make([][]bool, length)
for i := range c {
c[i] = make([]bool, length)
}
for gap := 0; gap < length; gap++ {
for i := 0; i < length - gap; i++ {
j := i + gap
if s[i] == s[j] && (j - i <= 2 || c[i + 1][j - 1]) {
c[i][j] = true
// find the longest
if j + 1 - i > len(longest) {
longest = s[i:j + 1]
}
}
}
}
return longest
}
- 时间复杂度：对二维状态数组(c)采取“之”字形赋值，增加gap来扩大子串长度；有两层for循环，故复杂度为(O(n^2)).
- 空间复杂度：开销在状态数组(c)上，为(O(n^2)).
分治法
回文串是左右对称的，如果从中心轴开始遍历，会减少一层循环。思路：依次以母串的每一个字符为中心轴，得到回文串；然后通过比较得到最长的那一个。注意：要考虑到像baccab这样的特殊子串，可以理解它的中心轴是cc。
// given a center, find the longest palindromic substring
func l2rHelper(s string, mid int) string {
l := mid - 1; r := mid + 1
length := len(s)
for r < length && s[r] == s[mid] {
r++
}
for l >= 0 && r < length && s[l] == s[r] {
l--
r++
}
return s[l+1:r]
}
func longestPalindrome(s string) string {
length := len(s)
longest := string(s[0])
for i := 0; i < length -1; i++ {
if len(l2rHelper(s, i)) > len(longest) {
longest = l2rHelper(s, i)
}
}
return longest
}
- 时间复杂度：对于给定中心，找出最长回文子串的复杂度为(O(n))；总的复杂度为(O(n^2)).
- 空间复杂度：(O(1)).
3. 参考资料
[1] programcreek, Leetcode – Longest Palindromic Substring (Java).
[2] GeeksforGeeks, Longest Palindromic Substring | Set 1.