Given a string S, find the longest palindromic substring in S. Note: This is Part II of the article: Longest Palindromic Substring . Here, we describe an algorithm (Manacher’s algorithm) which finds the longest palindromic substring in linear time. Please read Part I for more background information. In my previous post we discussed a total of four different methods, among them there’s a pretty simple algorithm with O(N2) run time and constant space complexity. Here, we discuss an algorithm that runs in O(N) time and O(N) space, also known as Manacher’s algorithm. Hint:
Read full article from Longest Palindromic Substring Part II | LeetCode
No comments:
Post a Comment