longest-palindromic-substring

about

you are given a string s, and you need found the longest palindromic substring about it

solution

this is a medium complex simulation algo，and it can be optmized by Dynamic programming

this is simulation stage code, not dunamic programmming

func longestPalindrome(s string) string {
	// 1、对每一点进行中央扩散 判断从该点延伸出去最大的回文川是多大
	res := ""
	runes := []rune(s)
	if len(runes) <= 1 {
		return s
	}
	for i := 0; i < len(runes); i++ {
		// 考虑两种情况
		// 1、奇数回文
		tempOddMaxString := getOddMaxString(runes, i)
		// 2、偶数回文
		tempEvenMaxString := getEvenMaxString(runes, i)
		tempMaxString := tempEvenMaxString
		if len(tempEvenMaxString) < len(tempOddMaxString) {
			tempMaxString = tempOddMaxString
		}
		if len(tempMaxString) > len(res) {
			res = tempMaxString
		}
	}
	return res
}

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

}

func getOddMaxString(runes []rune, i int) string {
	left, right := i, i
	for left >= 0 && right <= len(runes)-1 {
		left = left - 1
		right = right + 1
		if left < 0 || right >= len(runes) {
			return string(runes[left+1 : right])
		}
		if runes[left] != runes[right] {
			return string(runes[left+1 : right])
		}
	}
	return string(runes[left : right+1])
}