来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
给你一个字符串 s,找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。
示例 1:
输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。
示例 2:
输入:s = "cbbd"
输出:"bb"
提示:
1 <= s.length <= 1000
s 仅由数字和英文字母组成
本人提交代码
class Solution {
public:
string longestPalindrome(string A) {
// write code here
if( A.empty() )
return "";
int start = 0, end = 0;
int stringLen = A.size();
int maxLen = 0;
for ( int i = 0; i < stringLen; i++ )
{
// start with A[i];
int prev = i - 1, next = i + 1;
int len = 1;
// check continous char(s) same with A[i] 'aaaaaaa'
int count = 0;
int index = i + 1;
int _start = i;
int _end = i;
while ( index < stringLen )
{
if ( A[i] == A[index] )
{
count++;
index++;
}
else
break;
}
if ( count > 0 )
{
int currLen = count + 1;
len = currLen;
next = index;
i = index - 1;
_end = i;
}
while ( prev >= 0 && next < stringLen )
{
if ( A[prev] == A[next] )
{
len += 2;
_start = prev;
_end = next;
}
else
break;
if ( --prev < 0 )
break;
if ( ++next >= stringLen )
break;
}
if ( len > maxLen )
{
start = _start;
end = _end;
maxLen = len;
}
}
return A.substr( start, end - start + 1 );
}
};
本文由 BeijingJW 创作,采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
最后编辑时间为: Jun 2, 2023 at 05:28 pm