GO题解 | #最长回文子串#

go解题答案

• 思路概括：中点扩散法 因为如果是回文，则会两边对称，利用这一点规律去优化

• 思路核心：
  1、把字符串每个点当成是中点，然后向两边扩散比较

  func getLongestPalindromeSpread( A string ,  n int ) int {
  
    if n==0{
        return 0
    }
    res:=1 // 至少是1
    // 遍历中点
    for i:=0;i<n-1;i++ {  // 注意是n-1
        temp:=Max(spread(A,i,i),spread(A,i,i+1))
        res=Max(res,temp)
    }
    return res
  }
  func spread(s string,left int,right int)int {
    count:=len(s)
    for left>=0 && right<=count-1{
        if s[left]==s[right]{
            left--
            right++
        }else{
            break
        }
    }
    return right-left+1-2  //减2是因为先移动指针，再进行比较，所以break时要退回
  }

  go解题答案2

• 思路概括：动态规划

• 思路核心：
  1、状态转移 范围减1的字符串是回文，加1范围的也才可能是回文
  2、dp[left][right]=dp[left+1][right-1]

  func getLongestPalindrome( A string ,  n int)int {
    if n<2{
        return n
    }
    res:=1
    dp := make([][]bool, n+1)
    for a:=0;a<n+1;a++{
        dp[a]=make([]bool,n+1)
    }
    for right:=1;right<n;right++{
        for left:=0;left<n-1;left++{
            if A[left]!=A[right]{
                continue
            }
            if right==left{
                dp[left][right]=true
            } else if right - left <= 2{
                dp[left][right] = true
            }else {
                dp[left][right]=dp[left+1][right-1]
            } 
             if dp[left][right]==true {
                 res= Max(res,right-left+1)
             }
  
        }
  
    }
    return res
  }

  如果有帮助请点个赞哦， 更多文章请看我的博客

  题主背景

• 从业8年——超级内卷500Q技术经理——目前专注go和微服务架构