Skip to content

Latest commit

 

History

History
13 lines (7 loc) · 1002 Bytes

5.Ideas.md

File metadata and controls

13 lines (7 loc) · 1002 Bytes

思路

题目链接👈

首先,要明白judge函数作用是以一个中心向两侧扩展找到这个中心最长回文串的长度,参数left和right就是为了指定中心。

其次,中心可能是一个或两个字符。如:对于字符串“abcda”,“c”是中心;对于字符串“adccda”,“cc”是中心。

那么,judge(s, i, i)就是在找以 i(一个字符)为中心的最长回文串的长度;judge(s, i, i + 1)是在找以 i 和i+1(两个字符)为中心的最长回文串的长度。

将得到的两个长度和缓存的最长回文串长度相比较。若新得到的长度较长,表达式:start = i - (len - 1) / 2;end = i + len / 2; 就得出了新的最长回文串的开始和结束位置。

最后,for循环遍历了一遍,以一个字符为中心总共找了 n 次,以两个字符为中心总共找了 n-1 次,所以说“总共有2n−1 个这样的中心”。