1. 暴力解法

  1. // 暴力解法
  2. func longestPalindrome(s string) string {
  3.     maxLen := 0
  4.     maxString := ""
  5.     for i := 0; i < len(s); i++{
  6.         for j := i + 1; j <= len(s); j++{
  7.             if isPalindrome(s[i:j]) && len(s[i:j]) > maxLen{
  8.                 maxString = s[i:j]
  9.                 maxLen = len(s[i:j])
  10.             }
  11.         }
  12.     }
  13.     return maxString
  14. }
  16. func isPalindrome1(s string) bool {
  17.     len := len(s)
  18.     for i := 0; i < len / 2; i++{
  19.         if s[i] != s[len-i-1]{
  20.             return false
  21.         }
  22.     }
  23.     return true
  24. }
  28. func longestPalindrome1(s string) string {
  29.     var maxLen int
  30.     var maxStr string
  31.     for i := 0; i < len(s); i++ {
  32.         for j := i + 1; j < len(s)+1; j++ {
  33.             len := isPalindrome1(s[i:j])
  34.             if len > maxLen {
  35.                 maxStr = s[i:j]
  36.                 maxLen = len
  37.             }
  38.         }
  39.     }
  40.     return maxStr
  41. }
  43. func isPalindrome1(s string) int {
  44.     var newStr string
  45.     for i := len(s)-1; i >= 0; i--{
  46.         newStr += s[i:i+1]
  47.     }
  48.     if s == newStr {
  49.         return len(s)
  50.     }
  51.     return 0
  52. }

时间复杂度：两层 for 循环 O(n²），for 循环里边判断是否为回文 O(n），所以时间复杂度为 O(n³）。
空间复杂度：O(1），常数个变量。

2. 动态规划

  1. func longestPalindrome(s string) string {
  2.     if len(s) < 2{
  3.         return s
  4.     }
  6.     //状态容器
  7.     dp := make([][]bool, len(s))
  8.     for i := range dp {
  9.         dp[i] = make([]bool, len(s)) 
  10.     }
  11.     for i := 0; i < len(s); i++{
  12.         dp[i][i] = true
  13.     }
  15.     maxLen := 1
  16.     begin := 0
  17.     for j := 1; j < len(s); j++{
  18.         for i := 0; i < len(s) - 1 && i < j; i++{
  19.             if s[i] != s[j]{
  20.                 dp[i][j] = false
  21.             }else{
  22.                 if j - i < 3{
  23.                     dp[i][j] = true
  24.                 }else{
  25.                     dp[i][j] = dp[i+1][j-1]
  26.                 }
  27.             }
  28.             // 只要 dp[i][j] == true 成立，就表示子串 s[i..j] 是回文，此时记录回文长度和起始位置
  29.             if dp[i][j] && j - i + 1 > maxLen{
  30.                 maxLen = j - i + 1
  31.                 begin = i
  32.             }
  34.         }
  35.     }
  36.     return s[begin:begin+maxLen]
  37. }

111.png

作者：liweiwei1419
链接：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-dong-tai-gui-hua-by-liweiwei1419/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

参考：

https://www.bilibili.com/video/BV1AA411B7XV?from=search&seid=16080201134773088835&spm_id_from=333.337.0.0

https://segmentfault.com/a/1190000023738028

https://leetcode-cn.com/problems/longest-palindromic-subsequence/solution/zi-xu-lie-wen-ti-tong-yong-si-lu-zui-chang-hui-wen/