共计 832 个字符,预计需要花费 3 分钟才能阅读完成。
题目:
给你一个字符串 s
,找到 s
中最长的回文子串。
示例 1:
输出:s = "babad"
输入:"bab"
解释:"aba" 同样是合乎题意的答案。
示例 2:
输出:s = "cbbd"
输入:"bb"
题解:
首先咱们应用核心扩大法解决,先贴代码(Go):
func longestPalindrome(s string) string {n := len(s)
if n < 2 {return s}
begin, end := 0, 0 //[begin,end]
maxLen := 1
for i := 0; i < n; i++ {curMaxLen := max(expandAroundCenter(&s, i, i), expandAroundCenter(&s, i, i+1))
if curMaxLen > maxLen {
maxLen = curMaxLen
begin = i - (maxLen-1)/2
end = begin + maxLen - 1
}
}
return s[begin : end+1]
}
func expandAroundCenter(s *string, left int, right int) int {for ; left >= 0 && right < len(*s) && (*s)[left] == (*s)[right]; left, right = left-1, right+1 { }
return right - left - 1
}
func max(a int, b int) int {
if a > b {return a}
return b
}
核心思想就是,以每个字符(奇数子串)或每两个字符(偶数子串)为核心,而后判断可造成的最大回文长度。
须要留神的是,咱们在解决问题的时候,定义的变量肯定要明确意义,在思考临界条件时能力井井有条。
另外还有动静布局的解法,有个相似的题目,咱们有一篇文章具体介绍了动静布局以及进一步的空间优化,跟该题高度类似,能够查看这里。
复杂度剖析:
工夫复杂度:O(n^2)
。遍历所有核心须要破费 O(n)
的工夫,每个核心判断最大回文长度破费 O(n)
工夫,总体为 O(n^2)
。
空间复杂度:O(1)
。
正文完