LeetCode5最大回文子串（中心扩散法） _leetcode

丈夫志四海，万里犹比邻。这篇文章主要讲述LeetCode5最大回文子串（中心扩散法）相关的知识，希望能为你提供帮助。

一、题目
【LeetCode5最大回文子串（中心扩散法）】

提示：

1 < = s.length < = 1000
s 仅由数字和英文字母（大写和/或小写）组成

二、思路中心扩散法。
从每个节点开始，当前结点向两边扩散来判断回文串，因为回文串长度可能是奇数或者偶数，即后者就木有一个中心字符，伪代码应该如下：

for 0 < = i < len(s):
找到以 s[i] 为中心的回文串
找到以 s[i] 和 s[i+1] 为中心的回文串
更新答案

我们通过传入的左指针??l???和右指针??r???，可以同时处理回文串为奇数和偶数的情况。注意??palindrome???函数最后的??s.substr(l+1, r-1-l)???中，右边界是相对下标，其计算是：(r-1)-(l+1)+1=??r-l-1??。
三、代码

class Solution
public:
string longestPalindrome(string s)
string ans;
for(int i = 0; i < s.size(); i++)
//以s[i]为中心的最长回文子串
string s1 = palindrome(s, i, i);
//以s[i]和s[i+1]为中心的最长回文子串
string s2 = palindrome(s, i, i + 1);
//ans = longest(ans, s1, s2)
if(ans.size() < s1.size())
ans = s1;

if(ans.size() < s2.size())
ans = s2;

return ans;

string palindrome(string& s, int l, int r)
//防止索引越界
while(l > = 0 & & r < s.size() & & s[l] == s[r])
//向两边展开
l--; r++;

return s.substr(l + 1, r - l - 1);

;