> https://leetcode.com/problems/longest-palindromic-substring/description/

思路

直接暴力往两边搜索

func longestPalindrome(s string) string {
	buf := []byte(s)
	length := len(buf)
	if length == 0 {
		return s
	}

	start, end := 0, 0

	for ci, _ := range buf {
		i, j := ci, ci

				// 无法处理 "aaaa" 和 "noon" 这种情况
		for i > 0 && j < length - 1 && buf[i - 1] == buf[j + 1] {
			i--
			j++
		}

				// 考虑 "bba" 这种情况
		if i == j && ci > 0 && buf[ci] == buf[ci - 1] {
			i, j = ci-1, ci
		}

				// 考虑 "abb" 这种情况
		if i == j && ci < length - 1 && buf[ci] == buf[ci + 1] {
			i, j = ci, ci + 1
		}

		if i != j && j - i >= end - start {
			start, end = i, j
		}
	}
	return string(buf[start:end + 1])
}

上面代码无法处理 “aaaa” 和 “noon” 这种情况，只要把下面处理 “bba” 和 “abb” 情况的代码放到上面即可

func longestPalindrome(s string) string {
	buf := []byte(s)
	length := len(buf)
	if length == 0 {
		return s
	}

	start, end := 0, 0

	for ci, _ := range buf {
		i, j := ci, ci

		if i == j && ci > 0 && buf[ci] == buf[ci - 1] {
			i, j = ci-1, ci
		}

		if i == j && ci < length - 1 && buf[ci] == buf[ci + 1] {
			i, j = ci, ci + 1
		}

		for i > 0 && j < length - 1 && buf[i - 1] == buf[j + 1] {
			i--
			j++
		}

		if i != j && j - i >= end - start {
			start, end = i, j
		}
	}
	return string(buf[start:end + 1])
}

但上面又导致 “ccc” 无法处理，所以需要处理两种情况：

  1. 以当前字符为中心向两边扩散
  2. 以当前字符和下一个字符为中心向两边扩散

对比以上两个结果取大的那个，调整后如下

func longestPalindrome(s string) string {
	buf := []byte(s)
	length := len(buf)
	if length == 0 {
		return s
	}

	start, end := 0, 0

	for ci, _ := range buf {
		i, j := ci, ci
		for i > 0 && j < length - 1 && buf[i - 1] == buf[j + 1] {
			i--
			j++
		}

		if i != j && j - i >= end - start {
			start, end = i, j
		}

		i, j = ci, ci + 1
		if j < length && buf[i] == buf[j] {
			for i > 0 && j < length - 1 && buf[i - 1] == buf[j + 1] {
				i--
				j++
			}
			if i != j && j - i >= end - start {
				start, end = i, j
			}
		}
	}
	return string(buf[start:end + 1])
}