首页 > 代码库 > 【leetcode】Longest Palindromic Substring (middle) 经典

【leetcode】Longest Palindromic Substring (middle) 经典

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.

 

动态规划解法 O(n2) 超时

string longestPalindrome(string s) {        if(s.empty()) return s;        vector<vector<bool>> isPalindrome(s.length() + 1, vector<bool>(s.length() + 1, false));        string ans = s.substr(0,1);        for(int i = 0; i <= s.length(); i++) //长度        {            for(int j = 0; j <= s.length() - i; j++) //起始位置            {                if((i <= 1) || (isPalindrome[j + 1][i - 2] && s[j] == s[j + i - 1]))                {                    isPalindrome[j][i] = true;                    if(i > ans.length())                        ans = s.substr(j, i);                }            }        }        return ans;    }

 

O(N)解法 AC

string longestPalindrome2(string s)    {        if(s.empty()) return s;        string ss = "#";        for(int i = 0; i < s.length(); i++)        {            ss += s.substr(i, 1) + "#";        }        vector<int> P(ss.length()); //记录新字符串以每一个字符为中心时 包括中心的一半长度 只有一个时长度为1        string ans = s.substr(0,1);        int mx = 0; //向右最远的对称位置+1        int id = 0; //mx对应的中心位置        for(int i = 0; i < ss.length(); i++)        {            P[i] = (mx > i) ? min(P[2*id - i], mx - i) : 1;            while(i - P[i] >= 0 && i + P[i] < ss.length() && ss[i - P[i]] == ss[i + P[i]]) P[i]++;            if(P[i] - 1 > ans.length())                ans = s.substr((i - P[i] + 1)/2, P[i] - 1);            if(i + P[i] > mx)            {                mx = i + P[i];                id = i;            }        }        return ans;    }

 

【leetcode】Longest Palindromic Substring (middle) 经典