最长回文子串

in 知识共享 with 0 comment

来源:力扣(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 );
    }
};
Responses