（每日一练c++）CC144 最长的回文子串

ゞ浴缸里的玫瑰 2023-10-04 17:57 10阅读 0赞

### 描述 ###

找出给出的字符串S中最长的回文子串。假设S的最大长度为1000，并且只存在唯一解。

### 示例1 ###

输入：

"abcba"

复制返回值：

"abcba"

class Solution {
    public:
        string longestPalindrome(string s) {
            //字符串的长度
            int len = s.size();
            if (len == 0) return s;
            //保留最长回文串
            string resultStr = "";
            //回文子串长度为奇数,：对称点只有一个字符的情况
            for (int i=0; i<len; ++i){
                // i 为对称点
                int left = i;//左
                int right = i;//右
                //向左向右遍历，直到发现不相同的时候停止
                while (left > 0 && right < len - 1 && s[left - 1] == s[right + 1]){
                    --left;
                    ++right;
                }
                //比较，更新最长回文串
                if (right - left + 1 > resultStr.size()){
                    resultStr = s.substr(left, right - left + 1);
                }
            }
            
            //回文子串长度为偶数：对称点有两个字符
            for (int i = 0; i < len - 1; ++i){
                if (s[i] == s[i+1]){//两个对称点相同，才有继续遍历的意义
                    int left = i;
                    int right = i+1;
                    //向左向右遍历，直到发现不相同的时候停止
                	while (left > 0 && right < len - 1 && s[left - 1] == s[right + 1]){
                   		--left;
                    	++right;
                	}
                	//比较，更新最长回文串
                	if (right - left + 1 > resultStr.size()){
                    	resultStr = s.substr(left, right - left + 1);
                	}
                }
            }
            return resultStr;
        }
    };