算法
技术,  算法

最长回文子串 – LeetCode5

题目

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

示例1:
输入:s = "babad" 
输出:"bab" 
解释:"aba" 同样是符合题意的答案。
示例 2:
输入:s = "cbbd" 
输出:"bb"
示例 3:
输入:s = "a"
输出:"a"
示例 4:
输入:s = "ac"
输出:"a"

题解

golang:

func longestPalindrome(s string) string {
	if s == "" {
		return ""
	}

	start, end := 0, 0
	for i := 0; i < len(s); i++ {
		left1, right1 := expandAroundCenter(s, i, i)
		left2, right2 := expandAroundCenter(s, i, i + 1)
		if right1 - left1 > end - start {
			start, end = left1, right1
		}
		if right2 - left2 > end - start {
			start, end = left2, right2
		}
	}
	return s[start:end + 1]
}

func expandAroundCenter(s string, left int, right int) (int, int) {
	for ; left >= 0 && right < len(s) && s[left] == s[right]; left, right = left -1, right + 1 {}
	return left + 1, right - 1
}

相关链接

https://leetcode-cn.com/problems/longest-palindromic-substring/


精品课程


guest

0 评论
内联反馈
查看所有评论