Menu
Refer to this article on leetcode, there's a common mistake for solving the longest palindromic substring problem:
Reverse S and become S’. Find the longest common substring between S and S’, which must also be the longest palindromic substring.
For instance:
S = “abacdfgdcaba”, S’ = “abacdgfdcaba”.
The longest common substring between S and S’ is “abacd”. Clearly, this is not a valid palindrome.
But the following rectification I could not understand well. Could anyone explain it with an step-by-step procedure/example? Thanks!
To rectify this, each time we find a longest common substring candidate, we check if the substring’s indices are the same as the reversed substring’s original indices.
223
Manacher's algorithm is used to find the longest palindromic substring in any given string.
Approach: The simple approach is to check each substring whether the substring is a palindrome or not. To do this first, run three nested loops, the outer two loops pick all substrings one by one by fixing the corner characters, the inner loop checks whether the picked substring is palindrome or not.
longestPalin() function finds the longest palindrome word by extracting every word of the string and passing it to checkPalin() function. An extra space is added in the original string to extract last word. checkPalin() function checks if the word is palindrome. It returns true if word is palindrome else returns false.
The time complexity of the Dynamic Programming based solution is O(n^2) and it requires O(n^2) extra space. We can find the longest palindrome substring( LPS ) in (n^2) time with O(1) extra space.
I am stuck there, so I google to reach here. Now I understand.Let me take original String which the author mentioned as a example.
S = "caba', S' = "abac", so longest common substring is aba.
The sentence is "we check if the substring’s indices are the same as the reversed substring’s original indices."
1.What is the substring’s indices?
"aba" is [1, 2, 3]
2.what is reversed substring’s original indices? Reversed substring is "aba", and its original indices is also [1, 2, 3].
So that answer is correct.
And we are looking at another example.
S="abacdfgdcaba", S' = "abacdgfdcaba", so longest common substring is "abacd".
So same process:
1.What is the substring’s indices?
"abacd" is [0, 1, 2, 3, 4].
2.what is reversed substring’s original indices?
Reversed substring is "abacd", but its original indices is also [7, 8, 9, 10, 11].
So These two "abacd" is not same one, the answer is not correct.
I think that sentence is a bit tricky, and I think the author made it a little hard to understand.
I think the sentence should be changed to "To rectify this, each time we find a longest common substring candidate, we check if the substring are the same one as the reversed substring’."
197
answered Nov 02 '22 15:11
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With