每日一题---5. 最长回文子串[力扣][Go]-阿里云开发者社区

每日一题---5. 最长回文子串[力扣][Go]

2023-02-23 79

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 每日一题---5. 最长回文子串[力扣][Go]

题目描述

给你一个字符串 s，找到 s 中最长的回文子串。

解题思路

1.如何判断一个字符串是回文（从中间开始左右两边同时移动，如果左边等于右边就是回文串）

2.还有就是如何判断下标就是在中间（下标把整个字符串都遍历一遍才能找到最长的那个）

解题代码

暴力破解

所有例子都能通过，只是时间复杂度太高O（n^3）,超时

func isHuiWen(s string) bool {
  slen := len(s)
  for i,_ := range s {
    if s[slen - i -1] != s[i] {
      return false
    }
  }
  return true
}
func longestPalindrome(s string) string {
  frontIndex := 0
  afterIndex := 1
  frontIndexMax := 0
  afterIndexMax := 0
  len := len(s)
  for frontIndex <= len {
    for afterIndex <= len {
      s2 := s[frontIndex:afterIndex]
      if isHuiWen(s2) {
        if afterIndexMax - frontIndexMax < afterIndex - frontIndex {
          afterIndexMax = afterIndex
          frontIndexMax = frontIndex
        }
      }
      afterIndex ++
    }
    frontIndex ++
    afterIndex = frontIndex + 2
  }
  return s[frontIndexMax:afterIndexMax]
}

折中遍历法

func longestPalindrome02(s string) string {
  frontIndex := 0
  afterIndex := 0
  i := -1
  for i < len(s) - 1 {
    i++
    i := GetAns(i, s, &frontIndex, &afterIndex)
    i ++
  }
  return s[afterIndex:frontIndex + 1]
}
// 获取前标和后标
func GetAns(after int,s string,frontIndex *int,afterIndex *int) int {
  front := after
  i := len(s)
  for front < i - 1 && s[front + 1] == s[after] {
    front++
  }
  ans := front
  for after > 0 && front < i - 1 && s[front + 1] == s[after - 1] {
    after--
    front++
  }
  if *frontIndex - *afterIndex < front - after {
    *frontIndex = front
    *afterIndex = after
  }
  return ans
}