leetcode Longest Palindromic Substring

本是古典何须时尚 2022-08-05 00:51 131阅读 0赞

# 题目 #

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.  
题目来源：[https://leetcode.com/problems/longest-palindromic-substring/][https_leetcode.com_problems_longest-palindromic-substring]

# 分析 #

从某个元素开始，向两边扩散，在这个过程中求最大子串。有两种情况，第一种是”aba”，以一个元素为中心向两边扩充；第二种情况是“abba”，以两个元素为中心向两边扩充。这个算法复杂度怎么算？应该是最坏情况O(n^3)，平均情况O(n^2)吧。

# 代码 #

class Solution {
    public:
        string longestPalindrome(string s) {
            int len = s.length();
            if(len < 2)
                return s;
            string result = "";
            for(int i = 1; i < len-1; i++){
       //"aba"
                int t = 0;
                while(i-t >=0 && i+t <= len-1){
                    if(s.at(i-t) == s.at(i+t)){
                        t++;
                    }
                    else{
                        break;
                    }
                }
                string sub = s.substr(i-t+1, 2*t -1);
                if(result.length() < sub.length()){ 
                    result = sub;
                }
            }
            for(int i = 0; i < len-1; i++){
       //"abba"
                if(s.at(i) == s.at(i+1)){
                    int t = 0;
                    while(i-t >=0 && i+1+t <= len-1){
                        if(s.at(i-t) == s.at(i+1+t)){
                            t++;
                        }
                        else{
                            break;
                        }
                    }
                    string sub = s.substr(i-t+1, 2*t);
                    if(result.length() < sub.length()){ 
                        result = sub;
                    }
                }
            }
            return result;
        }
    };

[https_leetcode.com_problems_longest-palindromic-substring]: https://leetcode.com/problems/longest-palindromic-substring/