golang刷LeetCode[0005] 最长回文子串

风云风雨 · · 207 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

题目

给定一个字符串 s,找到 s 中最长的回文子串。你可以假定 s 的最大长度为1000.
示例1:

输入: babad
输出:bab
注意:aba也是有效答案

示例2:

输入:cbbd
输出:bb

题解

1、暴力法

func longestPalindrome(s string) string {
    var maxLen int
    var maxStr string
    for i := 0; i < len(s); i++ {
        for j := i + 1; j < len(s)+1; j++ {
            len := isPalindrome(s[i:j])
            if len > maxLen {
                maxStr = s[i:j]
                maxLen = len
            }
        }
    }
    return maxStr
}

func isPalindrome(s string) int {
    var newStr string
    for i := len(s)-1; i >= 0; i--{
        newStr += s[i:i+1]
    }
    if s == newStr {
        return len(s)
    }
    return 0
}

很显然,超时了。
时间复杂度:O(n3)
空间复杂度:O(1)

2、动态规划
如果子串 P 是回文子串,那么P(i,j)=(P(i+1,j-1) 且 S(i)=S(j))。
那么倒着查询就行

func longestPalindrome(s string) string {
    if len(s) < 2 {
        return s
    }
    // P[i][j]表示回文,P[i+1][j-1]也是回文
    longest := s[0:1]
    for i := 1; i < len(s); i++ {
        for rightStep := 0; rightStep < 2; rightStep++ {
            for p, q := i-1, i+rightStep; p >= 0 && q < len(s) && s[p] == s[q]; {
                if q-p+1 > len(longest) {
                    longest = s[p : q+1]
                }
                p--
                q++
            }
        }
    }
    return longest
}

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:风云风雨

查看原文:golang刷LeetCode[0005] 最长回文子串

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:1006366459

207 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传