[LeetCode] 5. 最长回文字串

题目描述：

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

题目链接：

. - 力扣（LeetCode）

解题主要思想：

固定一个中心，然后向两边走判断是否回文即可。主要注意的是回文串的中心有两种情况，一种是一个点，另一种是2个相同的点。

解题代码：

class Solution {
public:
    string longestPalindrome(string s) {
        int begin = 0, right = 0, len = 0;
        int size = s.size();
        for (int i = 0; i < size; ++i) {
            // 奇数的情况，即中心是一个点的情况
            int left = i, right = i;
            while (left >= 0 && right <= size && s[left] == s[right]) {
                --left;
                ++right;
            }
            if (right-left-1 > len) {
                begin = left + 1;
                len = right -left -1;
            }
            // 偶数的情况，即中心是两个相同的点的情况
            left = i, right = left + 1;
            while (left >= 0 && right <= size && s[left] == s[right]) {
                --left;
                ++right;
            }
            if (right-left-1 > len) {
                begin = left + 1;
                len = right -left -1;
            }
        }
        return s.substr(begin, len);
    }
};

原文地址：https://blog.csdn.net/weixin_65043441/article/details/142897762

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！