項(xiàng)目倉庫：
https://github.com/Benny66/leetcode.git

package algo

import (
    "fmt"
    "testing"
)

func TestLongestPalindrome(t *testing.T) {
    fmt.Println(longestPalindrome("aca"))
}

/*
    給你一個(gè)字符串 s，找到 s 中最長的回文子串。
    如果字符串的反序與原始字符串相同，則該字符串稱為回文字符串。
    示例 1：
        輸入：s = "babad"
        輸出："bab"
    解釋："aba" 同樣是符合題意的答案。
    示例 2：
        輸入：s = "cbbd"
        輸出："bb"
    提示：
        1 <= s.length <= 1000
        s 僅由數(shù)字和英文字母組成

解題思路：中心擴(kuò)散法
從一個(gè)點(diǎn)向兩邊擴(kuò)散
1、先向左邊走，當(dāng)左邊位置等于當(dāng)前位置，繼續(xù)向左邊走，直到不相等（left=curr）
2、然后向右邊走，當(dāng)右邊位置等于當(dāng)前位置，繼續(xù)向右邊走，直到不相等（right=curr）
3、判斷左邊位置和右邊位置是否相等，相等則繼續(xù)向兩邊走，直到不相等（left=right）
4、最后取當(dāng)前左移位置到右移位置到字符串為當(dāng)前點(diǎn)的最長回文字符串
注意：left和right分別不能小于0和超過字符串長度；
*/
func longestPalindrome(s string) string {
    length := len(s)
    if length == 0 {
        return s
    }
    var max int = 0
    var str string
    for cur := 0; cur < length; cur++ {
        left, right, llen, rlen := cur-1, cur+1, 0, 0
        // 1、先向左邊走，當(dāng)左邊位置等于當(dāng)前位置，繼續(xù)向左邊走，直到不相等（left=curr）
        for left > 0 && s[left] == s[cur] {
            left--
            //左移數(shù)+1
            llen++
        }
        // 2、然后向右邊走，當(dāng)右邊位置等于當(dāng)前位置，繼續(xù)向右邊走，直到不相等（right=curr）
        for right < length && s[right] == s[cur] {
            right++
            //右移數(shù)+1
            rlen++
        }
        // 3、判斷左邊位置和右邊位置是否相等，相等則繼續(xù)向兩邊走，直到不相等（left=right）
        for left >= 0 && right < length {
            if s[left] != s[right] {
                break
            }
            left--
            right++
            llen++
            rlen++
        }
        //長度大于最大的重新確定最長回文字符串
        if llen+rlen > max {
            max = llen + rlen
            str = s[cur-llen : cur+rlen+1]
        }
    }
    //默認(rèn)第一個(gè)字符
    if max == 0 {
        str = string([]byte(s)[0])
    }
    return str
}