最长回文子串

1. 题目描述

给你一个字符串 s，找到 s 中最长的回文子串。

2. 思路

• 暴力法
• 中心扩散法

3. 实现

3.1. 暴力法

func longestPalindrome(s string) string {
	max := 0
	maxStr := ""
	longestPalindrome2(s, 0, len(s)-1, &max, &maxStr)
	return maxStr
}

func longestPalindrome2(s string, left int, right int, max *int, maxStr *string) {
	if left > right {
		return
	}
	if isHuiWen(s, left, right) {
		current := right - left + 1
		if current > *max {
			*max = current
			*maxStr = s[left : right+1]
		}
	} else {
		longestPalindrome2(s, left+1, right, max, maxStr)
		longestPalindrome2(s, left, right-1, max, maxStr)
	}

}

func isHuiWen(str string, left int, right int) bool {
	for left < right {
		if str[left] != str[right] {
			return false
		}
		left++
		right--
	}
	return true
}

3.2. 中心扩散法

func longestPalindrome(s string) string {
    res := ""
    runes := []rune(s)
    for i, _ := range runes {
        str := spread(runes, i, i)
        if len(str) > len(res) {
            res = str
        }
        str = spread(runes, i, i+1)
        if len(str) > len(res) {
            res = str
        }
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a 
    }
    return b
}

func spread(runes []rune, left, right int) string {
    for left >= 0 && right < len(runes) {
        if runes[left] == runes[right] {
            left--
            right++
        }else {
            break
        }
    }
    return string(runes[left+1:right])
}

4. 参考

• 5. 最长回文子串 - 力扣（LeetCode）