0005.longest-palindromic-substring.md

0005.Longest-Palindromic-Substring

Description

Given two binary strings, return their sum (also a binary string).

The input strings are both non-empty and contains only characters 1 or 0.

Example 1:

Input: a = "11", b = "1"
Output: "100"

Example 2:

Input: a = "1010", b = "1011"
Output: "10101"

Tags: Math, String

题意

求最长回文子串

题解

思路1

暴力循环，挨个比对

func longestPalindrome(s string) string {
    if len(s) == 1 {
        return s
    }
    ans := ""
    ansLength := 0

    for i := 0; i < len(s); i++ {
        for j := len(s); j > i+ansLength; j-- {
            subString := s[i:j]
            if isPalindrome(subString) && len(subString) > ansLength {
                ans = subString
                ansLength = len(subString)
            }
        }
    }

    return ans
}

func isPalindrome(s string) bool {
    l := len(s)
    for i := 0; i < l/2; i++ {
        if s[i] != s[l-i-1] {
            return false
        }
    }

    return true
}

思路2

从中心开始向2遍比较

```go func longestPalindrome2(s string) string { if len(s) == 0 { return "" }

start, end := 0, 0
for i := 0; i < len(s); i++ {
    len1 := expandAroundCenter(s, i, i)
    len2 := expandAroundCenter(s, i, i+1)
    len := Max(len1, len2)

    if len > end-start {

        start = i - (len-1)/2
        end = i + len/2
    }
}

return s[start : end+1]

} func expandAroundCenter(s string, left, right int) int { L, R := left, right for L >= 0 && R < len(s) && s[L] == s[R] { L-- R++ }

return R - L - 1

} func Max(x, y int) int { if x > y { return x }

return y

}

### 思路3
> Manacher 算法
```go
// Manacher
func longestPalindrome(s string) string {
    return longestPalindromeLinear(s)
}

//    初始化Manacher需要的字符串
func initManacherStr(s string) string {
    ans := make([]rune, 0)
    ans = append(ans, '$')
    for i := 0; i < len(s); i++ {
        ans = append(ans, rune(s[i]), '$')
    }
    return string(ans)
}

//    Manacher
func longestPalindromeLinear(in string) string {
    /*
    *    初始化字符串，在字符串的没个字符左右都插入一个字符"$"
    *
    */
    s := initManacherStr(in)
    c, max := 0, 0


    /*
    *     P记录以每个字符为中心的最长回文串的信息
    *    P［id］记录的是以字符str［id］为中心的最长回文串
    *
    */
    //    P记录以每个字符为中心的最长回文串的信息
    P := make([]int, len(s))
    //for i := 0; i < len(P); i++ {
    //    P[i] = 0
    //}

    for i := 1; i < len(s)-1; i++ {
        i_mirror := 2*c - i
        if max > i {
            P[i] = Min(P[i_mirror], max-i)
        } else {
            P[i] = 0
        }

        for (i+P[i]+1) < len(s) && (i-P[i]-1) >= 0 &&
            s[i+P[i]+1] == s[i-P[i]-1] {

            P[i]++
        }

        if i+P[i] > max {
            c = i
            max = i + P[i]
        }


    }
    return extractLongest(in, P)
}

func extractLongest(s string, P []int) string {
    longestCenter, longestLength := 0, 0
    for i, v := range P {
        if v > longestLength {
            longestLength = v
            longestCenter = i
        }
    }
    offset := (longestCenter - longestLength) / 2
    return s[offset : offset+longestLength]
}

结语

如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：awesome-golang-algorithm