Longest Palindromic Substring

Description

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

Example:

Input: "babad"
Output: "bab"

Note: “aba” is also a valid answer.

Example:

Input: "cbbd"
Output: "bb"

从给定字符串中找出最长的回文子串

Solution

从最大长度开始判断是否回文,是则返回

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
func longestPalindrome(s string) string {
    maxLen := len(s)

    for l := maxLen; l > 0; l-- {
        for i := 0; i + l <= maxLen; i++ {
            lp, rp := i, i + l -1

            for lp < rp && s[lp] == s[rp] {
                lp++
                rp--
            }

            if lp >= rp {
                return s[i:i+l]
            }
        }
    }

    return s[0:1]
}

Similar Problem

3. Longest Substring Without Repeating Characters