LeetCode 5: Longest Palindromic
tags: String
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
Examples:
a → aabba → abbaaba → abaabbacc → abbaaabcacb → bcacb
Function:
public String longestPalindrome(String s) {
// Your Code
}
题目分析
该题目是字符串类型的Medium题目，要求找到字符串中最长的回文子串（LeetCode 3的题目中解释了substring和subsequence的区别），回文串就是顺序和逆序相同的字符串，如Examples所示。最朴素的想法是找到字符串的所有子串，查看每个子串是否是回文串，这种算法的时间复杂度是O(n3)，这里不再展示其实现（因为我也没想到这么朴素的想法O_O）。下面展示另外两种算法，第一个是枚举算法，另一个是Manacher算法，后者的时间复杂度都能达到O(n)，实在是查找回文串的不二选择。
算法1：枚举算法
public String longestPalindrome(String s) {
char[] chArray = s.toCharArray();
int len = chArray.length;
if (len < 2)
return s;
String result = s.substring(0, 1);
int minLength = 0;
for (int i=0; i<len-1; i++) {
if (chArray[i] == chArray[i+1]) {
int j=0;
while (i-j>=0 && i+1+j<len && chArray[i-j]==chArray[i+1+j]) {
j++;
}
if (minLength < j*2) {
minLength = j*2;
result = String.valueOf(chArray, i-j+1, minLength);
}
}
}
for (int i=1; i<len-1; i++) {
if (chArray[i-1] == chArray[i+1]) {
int j=1;
while (i-j>=0 && i+j<len && chArray[i-j]==chArray[i+j]) {
j++;
}
j--;
if (minLength < j*2+1) {
minLength = j*2+1;
result = String.valueOf(chArray, i-j, minLength);
}
}
}
return result;
}
该算法遍历字符串，以每个字符或两个一样的字符为中心，向两边查找对称字符，进而找到最长的字符串。代码中两个for循环分别查找以单字符和双字符为中心的回文串，这里不再赘述。下面分析一下该算法的时间复杂度，在for循环内部存在while循环，该循环判断两边的字符是否对称，其长度与n有关，所以时间复杂度应为O(n2)，该实现可以AC，运行时间中等。
算法2：Manacher算法
public String longestPalindromeWithManacher(String s) {
char[] chArray = s.toCharArray();
int len = chArray.length * 2 + 3;
char[] nch = new char[len];
nch[0] = '@'; // 3. 添加特殊字符，防止访问越界
nch[len-1] = '$';
for (int i=1; i<len-1; i++) {
if ((i & 1) != 0) {
nch[i] = '#'; // 1. 在字符串中添加特殊字符，将两种情况统一解决
} else {
nch[i] = chArray[(i>>1) - 1];
}
}
int[] p = new int[len];
int maxid = 0, center = 0, longest = 1, longestCenter = 0;
for (int i=1; i<len-1; i++) {
// 2. 算法的精华
if (maxid > i) {
p[i] = Math.min(p[2*center-i], maxid-i);
} else {
p[i] = 1;
}
while (nch[i-p[i]]==nch[i+p[i]]) {
p[i]++;
}
if (p[i]+i > maxid) {
maxid = p[i]+i;
center = i;
}
if (longest < p[i]) {
longest = p[i];
longestCenter = center;
}
}
StringBuilder sb = new StringBuilder();
for (int i=longestCenter+1-longest; i<longestCenter+longest; i++) {
if (nch[i] != '#')
sb.append(nch[i]);
}
return sb.toString();
}
在找该题目最优解法之前，我没听说过Manacher算法，而浏览的很多博客对该算法的理解和解释都很轻率，甚至有误，目前看到分析最认真准确的博客是acm_xyyh的博客。以下从3点讨论Manacher算法的关键和特殊的编程技巧。
- 在字符串中添加特殊字符，将两种情况统一解决。在算法1中需要处理单字符为中心和双字符为中心的情况，Manacher算法通过向其中插入分隔符（本例用的
#），将这两种情况转为单字符为中心的情况，即aba->#a#b#a#以b为中心，aa->#a#a#以#为中心。 - 算法的精华。对于遍历的每一个字符串，它有两种情况，处在某个回文串中和不在任何回文串中。对于后者，只能以该点为中心向两边比较；对于前者，应充分利用回文串的对称性，查看对称节点的回文长度提供当前节点回文长度，这里有3种情况，acm_xyyh的博文已介绍的很清晰，可以参考。
- 添加特殊字符，防止访问越界。这是一种编程技巧，在《编程珠玑》中也有介绍。添加这种字符的意义在于减少数据边界的比较次数，如算法1中在向两边检查对称性时都需要判断下标是否越界，而本算法利用特殊字符和字符比较即可跳出
while循环，能减少大量的下标越界检查，提高算法效率。
最后分析一下Manacher算法的时间效率，该算法需要遍历字符串，另一方面，算法只有遇到还没匹配的位置时才进行匹配，已匹配过的位置不再进行匹配，所以其时间复杂度为O(n)，超过了Java AC的99%。
总结
字符串类型的题目有很多高效但晦涩的算法，Manacher算法应该算一个，不过算法2的实现还有一些编程技巧上值得借鉴的地方：
- 利用处理数据的特殊性质，可以提供高效的解法；
- 对于需要分两种情况解决的方案，通常会有一种方法来优雅的合并，如上面插入的分隔符；
- 在数组中利用特殊数组防止数组访问越界。
