5/22 String, Palindrome 问题
Palindrome 的定义是，给定 S, S=S'
KMP 算法的核心是 failure function ，在 currect position 不匹配的情况下，在之前的substring中寻找最长的 suffix 后缀，使得它和 substring 中的 prefix 前缀相同。
考虑到总共可能的 palindrome 数量，我就先写了一个比较挫的写法，middle-out 由每个字符作为起点，往两边扫。
Palindrome 长度可能是奇数，也可能是偶数。所以指定 seed 往两边扩展的时候要注意先把 start / end 指针推到“不是 seed” 的位置上。
去 LeetCode 论坛看了一圈，发现他们用的写法也基本就是这么挫的。。
这个问题是有 O(n) 解法的，见 Manacher's Algorithm ， 不过对于面试的时间来讲要求有点太高了，就和要求你手写 KMP 一样。
public class Solution {
public String longestPalindrome(String s) {
if(s.length() <= 1) return s;
if(s.length() == 2){
if(s.charAt(0) == s.charAt(1)) return s;
else return s.substring(1);
}
int maxStart = 0;
int maxEnd = 0;
int maxLength = 1;
for(int i = 0; i < s.length(); i++){
int start = i - 1;
while(start >= 0 && s.charAt(start) == s.charAt(i)) start --;
int end = i + 1;
while(end < s.length() && s.charAt(end) == s.charAt(i)) end ++;
while(start >= 0 && end < s.length()){
if(s.charAt(start) == s.charAt(end)){
start --;
end ++;
} else {
break;
}
}
if(end - start - 1 > maxLength){
maxLength = end - start - 1;
maxStart = start + 1;
maxEnd = end - 1;
}
}
return s.substring(maxStart, maxEnd + 1);
}
}
Trivial problem. 稍微烦一点的地方在于我们要忽略字符，并且不区分大小写（原始 String 里有字符也有大小写）
ASC II 表里，一个字母的小写值与大写值的差正好是32 （小写字母值更大）
Character.isLetterOrDigit(char chr)
str.toLowerCase();
public class Solution {
public boolean isPalindrome(String s) {
if(s.length() <= 1) return true;
s = s.toLowerCase();
int start = 0;
int end = s.length() - 1;
while(start < end){
while(start < end && !Character.isLetterOrDigit(s.charAt(start)))
start ++;
while(start < end && !Character.isLetterOrDigit(s.charAt(end)))
end --;
if(s.charAt(start) == s.charAt(end)){
start ++;
end --;
} else {
return false;
}
}
return true;
}
}
Trivial problem. 扫一遍所有字符，如果出现过奇数次数的字符超过一个，就不能构造出 Palindrome 了。考察的就是一个简单的对 Palindrome 结构的理解。
public class Solution {
public boolean canPermutePalindrome(String s) {
if(s.length() <= 1) return true;
int[] hash = new int[256];
for(int i = 0; i < s.length(); i++){
int index = (int) s.charAt(i);
hash[index] ++;
}
boolean oneOdd = false;
for(int i = 0; i < 256; i++){
if(hash[i] % 2 == 0){
continue;
} else {
if(oneOdd) return false;
oneOdd = true;
}
}
return true;
}
}
下面的代码是一个比较粗暴的第一版本，因为要返回所有正确解，属于一个搜索问题。根据 palindrome 结构做 DFS + backtracking.
看了下论坛，发现别人的提交也都是这个思路。。
public class Solution {
public List<String> generatePalindromes(String s) {
int[] hash = new int[256];
for(int i = 0; i < s.length(); i++){
int index = (int) s.charAt(i);
hash[index] ++;
}
char center = '.';
boolean oneOdd = false;
for(int i = 0; i < 256; i++){
if(hash[i] % 2 == 0){
continue;
} else {
if(oneOdd) return new ArrayList<String>();
oneOdd = true;
center = (char) i;
hash[i] --;
}
}
char[] array = new char[s.length()];
List<String> list = new ArrayList<String>();
if(oneOdd) {
array[s.length() / 2] = center;
dfs(list, array, hash, s.length() / 2 - 1, s.length() / 2 + 1);
} else {
dfs(list, array, hash, s.length() / 2 - 1, s.length() / 2);
}
return list;
}
private void dfs(List<String> list, char[] array, int[] hash, int left, int right){
if(left < 0 || right >= array.length){
list.add(new String(array));
return;
}
for(int i = 0; i < 256; i++){
if(hash[i] <= 0) continue;
array[left] = (char) i;
array[right] = (char) i;
hash[i] -= 2;
dfs(list, array, hash, left - 1, right + 1);
array[left] = '.';
array[right] = '.';
hash[i] += 2;
}
}
}
这题在 LeetCode 上的标注难度为 "Hard".
我一开始的写法比较的简单粗暴，直接用写了一个 isPalindrome 函数去判断一个 substring 是不是 palindrome，然后从给定的 string 左面开始一直往右扫，去找到从最左边字符开始，最长的 palindrome，然后把剩下的右边部分复制一份，翻转，接到原来的 string 上.
但是超时了，时间复杂度太高。挂在了一个“aaaaaaaa...” 非常长但是结构非常简单的 test case 上。
这个思路是没有问题的，但是逐个 substring 去调用 O(n) 时间的函数还是时间复杂度太高了，没能有效利用 palindrome 的结构性质。
public class Solution {
public String shortestPalindrome(String s) {
if(s.length() <= 1) return s;
// Find the lonest palindrome starting from left most of string
int maxLength = 1;
for(int i = 1; i < s.length(); i++){
if(isPalindrome(s, 0, i)){
maxLength = Math.max(maxLength, i + 1);
}
}
StringBuilder sb = new StringBuilder(s.substring(maxLength));
String toAdd = sb.reverse().toString();
return toAdd + s;
}
private boolean isPalindrome(String s, int left, int right){
while(left < right){
if(s.charAt(left) != s.charAt(right)) return false;
left ++;
right --;
}
return true;
}
}
根据这个思路的另一种做法是，依然利用 longest palindrome 一定是从第一个字符开始的特点，从字符串末尾不断向起点逼近，寻找最终的位置。
如果出现 i j 位置的字符串不同的情况，则重置 i = 0 , j = end - 1 继续看。
不过本质上讲，这种做法和我刚才写的第一种没有任何区别，只不过是一个从里向外，一个从外向里。。。于是这个写法在 large test case 上依然 TLE，还没有利用好 substring 结构的精髓。
这个解法的代码是参考的 这个帖子 ，2015年9月写的，那个时候还没有大数据的 test case.
public class Solution {
public String shortestPalindrome(String s) {
if(s.length() <= 1) return s;
int i = 0;
int end = s.length() - 1;
int j = end;
StringBuilder sb = new StringBuilder();
while(i < j){
if(s.charAt(i) == s.charAt(j)){
i ++;
j --;
} else {
i = 0;
end --;
j = end;
}
}
return new StringBuilder(s.substring(end + 1)).reverse().toString() + s;
}
}
KMP 算法的核心是 next function ，在 currect position 不匹配的情况下，在之前的substring中寻找最长的 suffix 后缀，使得它和 substring 中的 prefix 前缀相同。
如果我们的字符串可以分拆成两段 S=QP， 我们想要求的是最长的 palindrome Q. 设 S′ 为 String S 的反序字符串，给定
SS′ = QPP′Q′ ，由于 Q 是 palindrome，可知 Q=Q′，二者分别是是 SS′ 的前缀与后缀，因此可以直接通过计算 SS′ 的 failure function 求出 Q 的最大长度。
这个问题能成功 AC 的关键就是。。一言不合就上 KMP !
第二天重写发现的问题：
Pattern 顺序不能错，是 SS' 而不是 S'S
public class Solution {
public String shortestPalindrome(String s) {
if(s.length() <= 1) return s;
int[] kmp = getKmpTable(s + "#" + new StringBuilder(s).reverse().toString());
int length = kmp[kmp.length-1];
return new StringBuilder(s.substring(length)).reverse().toString() + s;
}
private int[] getKmpTable(String pattern){
int M = pattern.length();
int[] next = new int[M];
int k = 0;
for (int q = 1; q < M; q++) {
while(k > 0 && pattern.charAt(k) != pattern.charAt(q)) {
k = next[k-1];
}
if (pattern.charAt(k) == pattern.charAt(q)) {
k++;
}
next[q] = k;
}
return next;
}
}