LeetCode 214. Shortest Palindrome - Stephen Wong的专栏 - 博客频道 - CSDN.NET
题意为，允许在字符串的头部添加字符，使其成为回文。最简单的方法是讲该字符串翻转为s2, s2 + s1即为回文，但题目要求的是最短的回文串。
于是问题便转换为一个，求以原字符串首字符开头(s[0])的最长子串的长度（亦即使得s.substr(0, length)为回文的最大length值）这么一个子问题。
―― 可以想象，当求得这么一个length后，我们将s.substr(length)翻转添加到s头部即为所求（亦即s.substr(length).reverse() + s即为所求）
这个子问题可暴力求解O(N^2)的复杂度，也可以用下述的Manacher算法在O(N)时间内求解。
Manacher算法实现了在O(N)时间内求字符串的最长回文子串(LeetCode 5. Longest Palindromic Substring)
在了解了该算法后，要求以原字符串首字符开头(s[0])的最长子串的长度，只要添加约束p[i] == i, 表示以i为中心回文串，其一边的长度为p[i].
若p[i] == i, 那么从i往前推p[i]个位置，那就是原点 ―― 所以这是一个包含原字符串s首字母s[0]的回文子串。
通过Manacher算法，求满足p[i] == i的最大i值即可。
Read full article from LeetCode 214. Shortest Palindrome - Stephen Wong的专栏 - 博客频道 - CSDN.NET
No comments:
Post a Comment