首页 > 代码库 > [LeetCode]5. Longest Palindromic Substring

[LeetCode]5. Longest Palindromic Substring

2024-10-13 15:55:39   214人阅读

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
 
Example:
Input: "babad"
Output: "bab"

 

Note: "aba" is also a valid answer.
Example:
Input: "cbbd"
Output: "bb"
 
给定一个字符串s，找到它的最长的回文子串。假设s的最大长度为1000。
例如:
输入："babad" 　　输出："bab"
输入："cbbd" 　　  输出："bb"
 
思路：回文序列要考虑它的奇偶问题。但如果我们把中间重复的部分看做是一个整体，那么就可以忽略这个问题。例如“abbba”和“abba”，把中间重复的b看作是一个整体c，那它们就都是“aca”，可以避开讨论奇偶。
class Solution {
public:
    string longestPalindrome(string s) {
        if(s.empty())return "";
        if(s.size()==1)return s;
        int maxLength=1,start=0;
        for(int i=0;i<s.size();){
            if (s.size() - i <= maxLength / 2) break;   //如果余下的长度小于当前最长回文子串长度的一半，也就不可能在出现比这个子串更长的回文子串了
            int k=i,j=i;                                
            while(k<s.size()-1&&s[k]==s[k+1]){          //重复的字符看作是一个整体，都跳过
                ++k;
            }
            i=k+1;                                      //调整下一次回文子串的中心位置
            while(k<s.size()-1&&j>0&&s[j-1]==s[k+1]){   //以这些个重复子串为中心，向两边散开，直到它们对应的值不同，就得到了一个回文子串
                --j;
                ++k;
            }
            int curLength=k-j+1;
            if(curLength>maxLength){
                maxLength=curLength;
                start=j;                                //记录这个回文子串的开始位置
            }
        }
        return s.substr(start,maxLength);
    }
};

 

[LeetCode]5. Longest Palindromic Substring


联系
我们