topic
leetcode: 5.?Longest Palindromic Substring
solution
Dynamic planning
Time complexity\(O(n^2)\), space complexity\(O(n^2)\)
See the code directly for the basic solution
class Solution {public: string longestPalindrome(string s) {int n = s.size(); vector> dp(n, vector(n, true)); int rx, ry; rx = ry = 0; for(int l = 1; l ry-rx){ ry = j; rx = i;}} else {dp[i][j ] = false;}}} return s.substr(rx, ry-rx + 1); }};
central diffusion method
Complicated time Degree\ (O(n^2)\), space complexity\(O(1)\)
We first assume that a certain point is the center Diffusion at both ends, find the longest palindrome substring centered on this point
class Solution {public: int rx, ry; void helper(string &s, int i, int offset) {int left = i; int right = i + offset; while(left >= 0 && right ry-rx){ ry = right-1; rx = left + 1;}} string longestPalindrome(string s) {int n = s.size(); rx = ry = 0; for(int i = 0; i
Manacher algorithm
Manacher algorithm is commonly known as "horse-drawn cart algorithm", time complexity\(O(n) \), space complexity \(O(n)\)
because palindrome strings have odd-length strings and even-length strings In order to better handle these two situations, you can insert a special character'#' in the string, so that the length of the new string becomes an odd length. For example, "aa" becomes "#a#a#". Add another special character'$' at the beginning of the string and'@' at the end, so that there is no need to deal with the problem of out-of-bounds (unified boundary processing).
Take "122112321" as an example and become "@#1" after the previous step #2#2#1#1#2#3#2#1#"
The Manacher algorithm uses an auxiliary array r[i] to represent the rightmost character of the longest palindrome centered on t[i]. The length of t[i], if the longest palindrome substring centered on t[i] is t[low, high], then r[i] = high-i + 1, t[low, high] = 2 * The r[i]-1, len array has a property, that is, r[i]-1 is the length of the palindrome substring in the original string. The proof is very simple. t[lowl, high] must start and end with "#" , The "#" inserted in this way is twice the number of characters in the original string and one more, so that the length of the longest palindrome string in the original string is r[i]-1, and the problem is converted to finding the longest r[ i]
Calculate len array
The algorithm mainly uses the characteristics of the existing palindrome substrings, reduces the search time, and calculates len from left to right [i], at the same time save the maximum value R of the right end point of the longest palindrome substring previously calculated and the corresponding center position c,
- i
\(\geq\) min(R-i + 1, p[j]), and then manually match the excess part
- i >= R, you can’t make any assumptions with future knowledge, you can only assume that it is at least 1, and then manually match
class Solution {public: string longestPalindrome(string s) {int n = s.size(); if(n == 0) return ""; string ns; ns.push_back('$'); for(int i = 0; i r(n); int c, R, C, MAX; R = -1; MAX = 0; C = 0; for(int i = 1; i R){ R = i + r[i]; c = i;} if(r[i]> MAX){ MAX = r[i]; C = i;}} return s.substr((C-MAX)/2, r[C]); }};
Time Complexity Analysis
Reference
- Manacher's ALGORITHM
- Leetcode: Longest Palindromic Substring String