golang力扣leetcode 5.最长回文子串

简介: golang力扣leetcode 5.最长回文子串

5.最长回文子串

5.最长回文子串

题解

题目:给你一个字符串 s,找到 s 中最长的回文子串

思路:

  1. 暴力,两重循环,第一层循环i作为起始,第二层循环j作为结束,判断字符串i到j是否是回文串
  2. 中心扩散,遍历字符串,以中心作为回文串中心,判断中心的两边,进行扩散
  3. dp,dp[i][j]为以i开始j结尾的字符串,如果s[i]==s[j],那么dp[i][j]=dp[i+1][j-1],这就是状态转移了,首先要枚举字串长度,再枚举左边界,如果反过来则有些状态是还没有确定的
  4. 马拉车算法,O(n)的复杂度,不搞竞赛学这个没什么意义,不写了

代码

//暴力
func longestPalindrome(s string) string {
  n := len(s)
  maxLen := 0
  ans := ""
  for i := 0; i < n; i++ {
    for j := i; j < n; j++ {
      if check(i, j, s) {
        if j-i+1 > maxLen {
          maxLen = j - i + 1
          ans = s[i : j+1]
        }
      }
    }
  }
  return ans
}
func check(l, r int, s string) bool {
  for ; l <= r; l, r = l+1, r-1 {
    if s[l] != s[r] {
      return false
    }
  }
  return true
}
//中心扩散
func longestPalindrome(s string) string {
  n := len(s)
  maxLen := 0
  ans := ""
  for i := 0; i < n; i++ {
    if cnt, ok := check1(i, s); ok {
      if cnt > maxLen {
        maxLen = cnt
        ans = s[i-(cnt-1)/2 : i+(cnt-1)/2+1]
      }
    }
    if cnt, ok := check2(i, i+1, s); ok {
      if cnt > maxLen {
        maxLen = cnt
        ans = s[i-(cnt-1)/2 : i+(cnt-1)/2+2]
      }
    }
  }
  return ans
}
func check1(l int, s string) (int, bool) {
  long := 0
  for i, j := l, l; i >= 0 && j < len(s); i, j = i-1, j+1 {
    if s[i] != s[j] {
      return long, true
    }
    long = j - i + 1
  }
  return long, true
}
func check2(l, r int, s string) (int, bool) {
  long := 0
  for i, j := l, r; i >= 0 && j < len(s); i, j = i-1, j+1 {
    if s[i] != s[j] {
      return long, true
    }
    long = j - i + 1
  }
  return long, true
}
//dp
func longestPalindrome(s string) string {
  n := len(s)
  // dp[i][j] 表示 s[i..j] 是否是回文串
  dp := make([][]bool, n)
  result := s[0:1]
  for i := 0; i < n; i++ {
    dp[i] = make([]bool, n)
    //所有长度为 1 的子串都是回文串
    dp[i][i] = true
  }
  //枚举子串长度
  for length := 2; length <= n; length++ {
    // 枚举左边界
    for i := 0; i < n; i++ {
      //确定右边界
      j := i + length - 1
      if j >= n {
        break
      }
      if s[i] == s[j] {
        if length <= 2 {
          dp[i][j] = true
        } else {
          dp[i][j] = dp[i+1][j-1]
        }
      } else {
        dp[i][j] = false
      }
      //dp[i][j] == true 成立,就表示子串 s[i..j] 是回文
      if dp[i][j] == true && j-i+1 > len(result) {
        result = s[i : j+1]
      }
    }
  }
  return result
}




目录
相关文章
|
15天前
|
算法
LeetCode算法题---最长回文子串、N 字形变换(四)
LeetCode算法题---最长回文子串、N 字形变换(四)
26 0
|
15天前
|
Java
【LeetCode力扣】面试题 17.14. 最小K个数(top-k问题)
【LeetCode力扣】面试题 17.14. 最小K个数(top-k问题)
17 1
|
9天前
|
机器学习/深度学习 canal NoSQL
从C语言到C++_12(string相关OJ题)(leetcode力扣)
从C语言到C++_12(string相关OJ题)(leetcode力扣)
20 0
|
15天前
|
存储 算法
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
8 0
|
15天前
leetcode代码记录(最长回文子串
leetcode代码记录(最长回文子串
12 2
|
15天前
|
存储 算法 Go
LeetCode第五题: 最长回文子串
给定一个字符串 `s`​,找到 `s`​ 中最长的回文子串。你可以假设 `s`​ 的最大长度为 1000。
LeetCode第五题: 最长回文子串
|
15天前
|
Go 容器 SQL
【Golang Leetcode】总目录(Day1~100)
【Golang Leetcode】总目录(Day1~100)
477 1
【Golang Leetcode】总目录(Day1~100)
|
15天前
|
Go
golang力扣leetcode 494.目标和
golang力扣leetcode 494.目标和
32 0
|
15天前
|
Go
golang力扣leetcode 剑指Offer II 114. 外星文字典
golang力扣leetcode 剑指Offer II 114. 外星文字典
24 0
|
15天前
|
监控 算法 Go
Golang深入浅出之-Go语言中的服务熔断、降级与限流策略
【5月更文挑战第4天】本文探讨了分布式系统中保障稳定性的重要策略:服务熔断、降级和限流。服务熔断通过快速失败和暂停故障服务调用来保护系统;服务降级在压力大时提供有限功能以保持整体可用性;限流控制访问频率,防止过载。文中列举了常见问题、解决方案,并提供了Go语言实现示例。合理应用这些策略能增强系统韧性和可用性。
71 0