最长回文子串

最长回文子串的解题思路

1. 中心扩散原则

   • 循环条件的设定为整个字符串长度的-2因为在查到最后一个元素的时候呀，他是没有比较的必要了，因为当循环到最后一个字符的时候就没有判断的必要了，最后一个字符没有向右扩散的字符了，这样就可以少循环一次

   • 大家知道回文串是分为奇数个和偶数个的，所以有两种的情况奇数和偶数的情况。

   • 最后一个要想的就是当找出最长的回文子串的时候，我们应该去寻找他 的其实坐标 ，以便我们返回，首先我们从中心开始找的意思就是==i==就是我们要找的中心其次我们找到回文子串的最长长度，我们可以可利用回文子串的长度，来求初始坐标，我们先将长度/2得到一半的回文子串-1，因为坐标从0开始所以-1，然后用i-刚才算的得到初始坐标。

   代码实例

   // 回文子串的长度
   func expandAroundCenter(s string, left, right int) int {
     length := len(s)
     i, j := left, right
     for i >= 0 && j < length {
       if string(s[i]) == string(s[j]) {
         i--
         j++
       } else {
         break
       }
     }
     return j - i - 1
   }
   //最大值
   func Max(i, j int) int {
     if i > j {
       return i
     }
     return j
   }
   func longestPalindrome(s string) string {
     length := len(s)
     if length <= 1 {
       return s
     } else {
       maxLne, begin := 1, 0
       for i := 0; i < length-1; i++ {
         oddLen := expandAroundCenter(s, i, i)    //奇数的情况
         evenLen := expandAroundCenter(s, i, i+1) //偶数的情况
         curMaxLen := Max(oddLen, evenLen)
         if curMaxLen > maxLne {
           maxLne = curMaxLen
           begin = i - (maxLne-1)/2
         }
       }
       return s[begin : begin+maxLne]
     }
   }
   func main() {
     s := "babad"
     fmt.Println(longestPalindrome(s))
   }

1. 动态规划解法

   • 动态规划思路可能不太那么容易相同，也是所有算法思想中最难的，所谓的动态规划思想，一般是先优先计算出小部分的最优解然后再计算大部分的算法。这道题使用动态规划的思路大概如下首先根据回文串的特点，i==j的。这样我们就可以列一个表来记录一下回文子串的匹配情况,我们可以确定的是在i=j行一定是true，假设s="aba"我们就有了下面的一个表

   	0	1	2
   0	true	false	True
   1		true	False
   2			true

   • 因为是回文子串我们只需要算上半个表即可，要想满足状态转移方程，我们最后是按列进行计算这样就可以保证状态转移方程得正确。

func longestPalindrome(s string) string {
  length := len(s)
  if length <= 1 {
    return s
  } else {
    maxLen, begin := 1, 0
    dp := make([][]bool, length)
    for i := 0; i < length; i++ {
      dp[i] = make([]bool, length)
    }
    //填表（对角线因为是一个字符所以一定是true)
    for i := 0; i < length; i++ {
      dp[i][i] = true
    }
    for j := 1; j < length; j++ {
      for i := 0; i < j; i++ {
        if s[i] != s[j] { //因为是按列走所以当元素不相等时填入false
          dp[i][j] = false
        } else {
          if j-i < 3 { //在j-i小于3的时候一个是回文子串所以直接填true
            dp[i][j] = true
          } else {  //在中间的距离大于三的时候就需要用到状态转移方程了
            dp[i][j] = dp[i+1][j-1]
          }
        }
        //
        if dp[i][j] && j-i+1 > maxLen {
          maxLen = j - i + 1
          begin = i
        }
      }
    }
    return s[begin : begin+maxLen]
  }
}

上面的两种解法，最快的是一种解法，动态规划的解法，其实和暴力解法差了一个平方，动态规划大概是n2 只是在暴力解法的基础上进行了剪枝的操作模，而第一种解法把复杂度控制在了n，准确来说是2n一般省略掉2所以为n。还有一种比较难的解法叫做Manacher算法，把复杂度控制在了n，线性复杂度的程度，因为实现复杂度较高，一般不要求能够手写出来。