5. Longest Palindromic Substring

Leetcode 链接

题目

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

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:

Input: "cbbd"
Output: "bb"

题意解析

找出最长回文子串

解决方案一

• 在每个字符的左右两边加上特殊字符 "#"，从而使得字符串长度变为奇数。例 1)：abba =》 #a#b#b#a# 例 2): aba => #a#b#a#
• 以每一个字符为中心，开始向两边寻找，判断两边的字符是否相等，如果相等则继续向两边扩展，如果不相等则结束此次搜索

Go 代码一

type Result struct{
    pos, length int
}

func longestPalindrome(s string) string {
    res := Result{
        pos : 0,
        length : 0,
    }

    str := "#"
    for _, v := range s {
        str += string(v) + "#"
    }

    tmpRune := []rune(str)
    for i:=0; i< len(str); i++ {
        tmpLen := check(tmpRune, i)   
        if tmpLen > res.length {
            res.length = tmpLen
            res.pos = i
        }
    }

    resStr := str[res.pos - res.length : res.pos + res.length + 1]

    return strings.Replace(resStr, "#", "", -1)
}

func check(tmp []rune , pos int) int{
    length := 0
    from := pos-1
    to := pos+1

    for from>=0 && to<len(tmp) && tmp[from] == tmp[to] {
        length += 1
        from--
        to++
    }    

    return length
}