前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
社区首页 >专栏 >Go算法实战 - 5.【最长回文子串LeetCode-5】

Go算法实战 - 5.【最长回文子串LeetCode-5】

作者头像
junedayday
发布2021-08-05 10:44:59
发布2021-08-05 10:44:59
33000
代码可运行
举报
文章被收录于专栏:Go编程点滴Go编程点滴
运行总次数:0
代码可运行

Leetcode-5 最长回文子串

原题链接 https://leetcode-cn.com/problems/longest-palindromic-substring/

代码语言:javascript
代码运行次数:0
运行
复制
func longestPalindrome(s string) string {
}

这道题中,我们也要注意奇数和偶数的边界情况。

基本解法

枚举所有情况

刚拿到这道题时,我们很容易想到一个解法:

  • 枚举出s所有的子字符串
  • 找到最长的回文串

这个解法代码我就不专门写了,复杂度很高,但如果你想不到解决方案时,可以先写出这个解法,再逐步优化。

利用递归拆分成子问题

代码语言:javascript
代码运行次数:0
运行
复制
func longestPalindrome(s string) string {
    if len(s) <= 1 {
        return s
    }

    // 查找以s[0]为开头的最长回文子串
    right := len(s)
    for ; right >= 0; right-- {
        // 找到最长的回文子串就退出
        if isPalindrome(s[:right]) {
            break
        }
    }

    // 用递归的方式获取s[1:]的长度,与上面的结果对比
    subS := longestPalindrome(s[1:])
    if len(subS) > right {
        return subS
    }
    return s[:right]
}

// 头尾两个指针不断往中间缩进
func isPalindrome(s string) bool {
    if len(s) <= 1 {
        return true
    }
    left, right := 0, len(s) - 1
    
    // 如果s长度为奇数,退出时刚好left=right,偶数则为 left > right
    for left < right {
        if s[left] != s[right] {
            return false
        }
        left++
        right--
    }
    return true
}

这个解法的代码思路相对清晰,核心思路是将 以s[0]开头的回文字符串s[1:]中最长回文子串 进行对比,其中后者是递归的子问题。

在有一定的算法基础后,我个人比较喜欢先用 递归思路去简化问题,将代码拆分成子问题,能大量地简化代码。

进阶解法

利用对称点

从回文串的特点来看,它存在一个对称点:

  • 长度为奇数2n+1的字符串,对称点为第n+1个字符
  • 长度为偶数2n的字符串,对称点为第n与n+1个字符之间,我们不妨命名为空白blank

所以,我们就对字符串s进行遍历,查找它的每个对称点上最长的回文串

代码语言:javascript
代码运行次数:0
运行
复制
func longestPalindrome(s string) string {
 var longest string
 // 是否为空白
 // 我们把字符串s看作为:s[0]-blank-s[1]-...-s[n-1]
 var isBlank bool
 var mid int

 for mid < len(s) {
  var sub string
  if isBlank {
   // 空白的话,我们认为这个空白是在mid-1和mid之间的,从两边开始对比
   sub = findLongestPalindromeByMid(s, mid-1, mid)
   isBlank = false
   mid++
  } else {
   // 非空白的话,从索引mid的两边开始对比
   sub = findLongestPalindromeByMid(s, mid-1, mid+1)
   isBlank = true
  }
  if len(sub) > len(longest) {
   longest = sub
  }
 }
 return longest
}

func findLongestPalindromeByMid(s string, left, right int) string {
 // left和right就是两个指针,不断往两边移动,直到找到不相同的两个字符
 for left >= 0 && right < len(s) {
  if s[left] != s[right] {
   break
  }
  left--
  right++
 }

 // 注意这里的索引,很容易搞混,我们要取的是left+1到right-1,这里切片后面的索引为right
 return s[left+1 : right]
}

简化空白的处理

从上面的代码来看,空白的处理挺麻烦,我们可以直接从代码结构去优化。

大家可以仔细的阅读isBlank相关的代码,可以直接消除这个变量:

代码语言:javascript
代码运行次数:0
运行
复制
func longestPalindrome(s string) string {
    var longest string
    var mid int 
    
    for mid < len(s) {
        // 对称点为某个字符,长度为奇数
        sub := findLongestPalindromeByMid(s, mid-1, mid)
        if len(sub) > len(longest) {
            longest = sub
        }
        
        // 对称点为空白,长度为偶数
        sub = findLongestPalindromeByMid(s, mid-1, mid+1)
        if len(sub) > len(longest) {
            longest = sub
        }
        mid++
    }
    return longest
}

func findLongestPalindromeByMid(s string, left, right int) string {
    for left >= 0 && right < len(s) {
        if s[left] != s[right] {
            break
        }
        left--
        right++
    }

    return s[left+1:right]
}

动态规划

动态规划是算法中大量出现的一个解法,我们以这道题为例,进行探索。

动态规划的细节请自行搜索,如 https://www.zhihu.com/question/39948290

动态规划解法

代码语言:javascript
代码运行次数:0
运行
复制
func longestPalindrome(s string) string {
 // 边界条件判断
 length := len(s)
 if length <= 1 {
  return s
 }

 // 回文子串至少为1,即单个字符
 begin, maxLen := 0, 1
 // 动态规划的关键数组dp
 var dp = make([][]bool, length)
 for k1 := range dp {
  dp[k1] = make([]bool, length)
  for k2 := range dp[k1] {
   // 初始化均为false
   dp[k1][k2] = false
  }
  // 单个字符默认为回文串
  dp[k1][k1] = true
 }

 for size := 2; size <= length; size++ {
  for start := 0; start <= length-size; start++ {
   end := start + size - 1

   // 如果首位字符串相同
   if s[start] == s[end] {
    if size == 2 {
     // 边界情况,即只有2个字符且相等
     dp[start][end] = true
    } else {
     // 核心:动态规划的核心推导函数
     dp[start][end] = dp[start+1][end-1]
    }
   }

   // 更新最长回文子串
   if dp[start][end] && size > maxLen {
    maxLen = size
    begin = start
   }
  }
 }
 return s[begin : begin+maxLen]
}

最核心的公式为dp[start][end] = dp[start+1][end-1],其余都是对边界条件的处理。

但运行结果的效率偏低

  • 执行用时:104 ms, 在所有 Go 提交中击败了42.53%的用户
  • 内存消耗:7 MB, 在所有 Go 提交中击败了24.68%的用户

优化1 优化条件分支

我们分析一下上面的代码:从空间复杂度来看,动态规划的数组dp是不可或缺的,所以减少内存消耗比较困难了。

因此,我们把目光放在执行时间上,那么重点就是for循环里的代码复杂度。

我们注意到一个关键的变量dp[start][end],对它进行改造

代码语言:javascript
代码运行次数:0
运行
复制
func longestPalindrome(s string) string {
 length := len(s)
 if length <= 1 {
  return s
 }

 begin, maxLen := 0, 1
 var dp = make([][]bool, length)
 for k1 := range dp {
  dp[k1] = make([]bool, length)
  for k2 := range dp[k1] {
   dp[k1][k2] = false
  }
  dp[k1][k1] = true
 }

 for size := 2; size <= length; size++ {
  for start := 0; start <= length-size; start++ {
   end := start + size - 1

   if s[start] == s[end] {
    if size == 2 || dp[start+1][end-1] {
     dp[start][end] = true
     // 减少if-else的分支判断次数
     if size > maxLen {
      maxLen = size
      begin = start
     }
    }
   }
  }
 }
 return s[begin : begin+maxLen]
}

效果很明显,代码执行时间减少

  • 执行用时:72 ms, 在所有 Go 提交中击败了50.93%的用户
  • 内存消耗:7 MB, 在所有 Go 提交中击败了28.37%的用户

优化2 分析循环内代码执行逻辑

我们继续看代码里的size > maxLen条件,发现会出现如下情况:

  • 如果一个字符有多个相同size的回文子串,这个if内的语句会被执行多次
  • 但我们只需要获得最长的回文子串之一,所以只需要记录第一次即可

于是我们尝试改造:

代码语言:javascript
代码运行次数:0
运行
复制
func longestPalindrome(s string) string {
 length := len(s)
 if length <= 1 {
  return s
 }

 begin, maxLen := 0, 1
 var dp = make([][]bool, length)
 for k1 := range dp {
  dp[k1] = make([]bool, length)
  for k2 := range dp[k1] {
   dp[k1][k2] = false
  }
  dp[k1][k1] = true
 }

 for size := 2; size <= length; size++ {
  // 用来表示对应size的字符串已经找到
  founded := false
  for start := 0; start <= length-size; start++ {
   end := start + size - 1
   if s[start] == s[end] {
    if size == 2 || dp[start+1][end-1] {
     dp[start][end] = true
     // 只记录第一个即可
     if !founded && size > maxLen {
      maxLen, begin = size, start
      founded = true
     }
    }
   }
  }
 }
 return s[begin : begin+maxLen]
}
  • 执行用时:80 ms, 在所有 Go 提交中击败了49.30%的用户
  • 内存消耗:7 MB, 在所有 Go 提交中击败了31.54%的用户

然而,执行结果告诉我们这部分的优化无明显效果,甚至还降低了评分。但我们无需沮丧,因为这道题针对的是小规模场景的算法题,这个思路可能在大规模的计算场景下带来很明显的提升

总结

Leetcode第五题的难度不高,也让我们初次接触了 动态规划 这个思路。

同时,我们也遇到了一个**“失败的优化案例”**。这也从侧面告诉了我们,抛开具体场景的优化都是不可靠的

Github: https://github.com/Junedayday/code_reading Blog: http://junes.tech/ Bilibili: https://space.bilibili.com/293775192 公众号: golangcoding

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-07-22,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Go编程点滴 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Leetcode-5 最长回文子串
  • 基本解法
    • 枚举所有情况
    • 利用递归拆分成子问题
  • 进阶解法
    • 利用对称点
    • 简化空白的处理
  • 动态规划
    • 动态规划解法
    • 优化1 优化条件分支
    • 优化2 分析循环内代码执行逻辑
  • 总结
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档