算法解读-最长回文字符串（Go）

题目描述

LeetCode#5

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

解题-中心扩展算法

//求最长回文字符串
//中心扩展算法
func longestPalindrome(s string) string {
    start := 0
    end := 0
    var len1, len2, len int
    //排除s长度<=1的情况
    if utf8.RuneCountInString(s) < 1 {
        return ""
    }
    //避免超时（LeetCode提交时会有超时的情况，比如出现1000个'b'构成的字符串,此步骤可避免）
    if s == reverse(s) {
        return s
    }
    if utf8.RuneCountInString(s) == 1 {
        return s
    }
    //循环调用中心扩展算法
    for i := 0; i < utf8.RuneCountInString(s)-1; i++ {

        len1 = centerexpand(s, i, i)
        len2 = centerexpand(s, i, i+1)
        if len1 >= len2 {
            len = len1
        } else {
            len = len2
        }
        if len > end-start {
            start = i - (len-1)/2
            end = i + len/2
        }
    }
    return s[start:(end + 1)]
}

//中心扩展算法
func centerexpand(s string, left int, right int) int {
    for left >= 0 && right < utf8.RuneCountInString(s) && s[left] == s[right] {
        left--
        right++
    }
    return right - left - 1
}

//字符串反转
func reverse(src string) string {
    dst := []rune(src)
    len := len(dst)
    var result []rune
    result = make([]rune, 0)
    for i := len - 1; i >= 0; i-- {
        result = append(result, dst[i])
    }
    return string(result)
}

解读

1. rune数据类型？

2. Golang 与python中的字符串反转

   在go中，需要用rune来处理，因为涉及到中文或者一些字符ASCII编码大于255的。

   func main() {
   
     fmt.Println(reverse("Golang python"))
   
   }
   func reverse(src string) string {
     dst := []rune(src)
     len := len(dst)
     var result []rune
     result = make([]rune, 0)
     for i := len - 1; i >= 0; i-- {
      result = append(result, dst[i])
     }
     return string(result)
   }

   而在python中，有几种方法，一个是list的操作，一个是系统的自带的函数，还有一个采用上面的遍历的方法

   #方法1--------------------------------------
   s = 'Golang python'
   print (s[::-1])
   
   #方法2--------------------------------------
   s = 'Golang python'
   l = list(s)
   l.reverse()
   print (''.join(l) )
   
   #方法3--------------------------------------
   s = 'Golang python'
   str=[]
   k=0
   for i in s:
     str.append(s[len(s)-1-k])
     k=k+1
   print (''.join(str) )
   
   #方法4--------------------------------------
   s = 'Golang python'
   str=[]
   for i in s:
     str.insert(0,i)
   print (''.join(str) )

3. Golang 与python中的字符串长度

4. 中心扩展算法

   回文中心的两侧互为镜像， 因此，回文可以从它的中心展开，并且只有 （2n−1） 个这样的中心。

   你可能会问，为什么会是 2n −1 个，而不是 n 个中心？原因在于所含字母数为偶数的回文的中心可以处于两字母之间（例如 \textrm{“abba”}“abba” 的中心在两个 \textrm{‘b’}‘b’ 之间）。

。