Description

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Input: "babad"
Output: "bab"

Note: "aba" is also a valid answer. 
Input: "cbbd"
Output: "bb"


Ideas

定義一個function來取得“從當前字符向左右展開”的最長對稱字符串。

然後scan整個字符串並比較當前取得的對稱字符串是否比紀錄的長度還長,是的話就更新。

注意點是對稱字符串有可能是最中間有兩個相同的字符,所以每個位置需要找兩字最長對稱字符串。


Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func longestPalindrome(s string) string {
    res := ""
    var tmp string
    for i, _ := range s {
        tmp = helper(i, i, s)
        if len(tmp) > len(res) {
            res = tmp
        }
        tmp = helper(i, i + 1, s)
        if len(tmp) > len(res) {
            res = tmp
        }
    }
    return res
}

func helper(l, h int, s string) string {
    for l >= 0 && h < len(s) && s[l] == s[h] {
        l--
        h++
    }
    return s[l+1:h]
}