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.
-------------------------------------------
Solution#1 O(n^2),
there are (2n - 1) centers for all possible palindromes
class Solution { public: void pal (string s, int &left, int &right, int &maxLeft,int &maxRight) { while (left >= 0 && right < s.length()) { if (s[left] == s[right]) { left--; right++; }else { break; } } if (maxRight - maxLeft < right - left - 2) { maxLeft = left + 1; maxRight = right - 1; } } string longestPalindrome(string s) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. if (s.length() == 1) return s; int maxLeft = 0; int maxRight = 0; int center = 1; int max = 0; for (;center < s.length(); center++) { int left = center - 1; int right = center; pal(s,left,right,maxLeft,maxRight); // even left = center - 1;; right = center + 1; pal(s,left,right,maxLeft,maxRight); // odd } return s.substr(maxLeft,maxRight - maxLeft + 1); } };Solution#2 O(n)
http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html
Jun-27-2015
Manacher's algorithm
class Solution { public: string processString(string s) { if (s.length() == 0) return s; string rt = ""; for (int i = 0; i < s.length(); i++) { rt = rt + "#" + s[i]; } rt += '#'; return rt; } string longestPalindrome(string s) { string t = processString(s); vector<int> p(t.length(),0); int center = 1, rightExpand = 1; for (int i = 1; i < t.length(); i++) { int i_mirror = center - (i - center); if (rightExpand > i) { p[i] = min(rightExpand - i,p[i_mirror]); } while (i + 1 + p[i] > 0 && i + 1 + p[i] < t.length() && t[i + 1 + p[i]] == t[i - 1 - p[i]]) { cout << p[i] << endl; p[i]++; } if (i + p[i] > rightExpand) { rightExpand = i + p[i]; center = i; } } int longest = 0; int index = 0; for (int i = 0; i < p.size(); i++) { if (longest < p[i]) { index = i; longest = p[i]; } } return s.substr((index - longest) / 2, longest); } };
No comments:
Post a Comment