0005-longest-palindromic-substring.adoc

5. Longest Palindromic Substring

LeetCode - Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

解题分析

最简单的方式：使用两个指针，把字符串逐个"拆成"子串，然后留下最大子串即可。可惜，这种算法的时间复杂度是 O(n³)。

没想到，竟然存在时间复杂度为 O(n) 的算法：Manacher’s Algorithm。在维基百科上有解释： Longest palindromic substring - Wikipedia。回头研究研究再补充！

另外，这道题还可以练手动态规划。

参考资料

• Manacher’s Algorithm - Linear Time Longest Palindromic Substring - Part 1 - GeeksforGeeks

• Manacher’s Algorithm - Linear Time Longest Palindromic Substring - Part 2 - GeeksforGeeks

• Manacher’s Algorithm - Linear Time Longest Palindromic Substring - Part 3 - GeeksforGeeks

• Manacher’s Algorithm - Linear Time Longest Palindromic Substring - Part 4 - GeeksforGeeks

• Manacher’s Algorithm Explained— Longest Palindromic Substring

• Manacher算法总结_ddyyxx的程序员之路-CSDN博客

• Manacher算法详解 - 简书

link:{sourcedir}/_0005_LongestPalindromicSubstring.java[role=include]