欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode 5. Longest Palindromic Substring

程序员文章站 2024-03-23 11:44:58
...

题目链接 最长回文子串 - 力扣 (LeetCode)

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

题目范围小于1000所以可以用n^2的算法
枚举中心点,用两个指针向两个方向遍历
要分为回文字串长度是奇数和偶数的情况

class Solution {
public:
    string longestPalindrome(string s) {
        int len = -1;
        string ans;
        for(int pos = 0; pos < s.size(); ++ pos){
            // 回文字串长度为偶数
            int i = pos, j = pos + 1;
            while(~i && j < s.size() && s[i] == s[j]) i --, j ++;
            if(j - i - 1 > len){
                len = j - i - 1;
                ans = s.substr(i + 1, len);
            }
            
            i = pos - 1, j = pos + 1;
            while(~i && j < s.size() && s[j] == s[i]) i --, j ++;
            if(j - i - 1 > len){
                len = j - i - 1;
                ans = s.substr(i + 1, len);
            }
        }
        return ans;
    }
};