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(n3)。
• 空间复杂度：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]≠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(n2).
• 空间复杂度：开销在状态数组c上，为O(n2).

分治法

回文串是左右对称的，如果从中心轴开始遍历，会减少一层循环。思路：依次以母串的每一个字符为中心轴，得到回文串；然后通过比较得到最长的那一个。注意：要考虑到像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(n2).
• 空间复杂度：O(1).

3. 参考资料

[1] programcreek, Leetcode – Longest Palindromic Substring (Java).
[2] GeeksforGeeks, Longest Palindromic Substring | Set 1.