Palindrome 问题

5/22 String, Palindrome 问题

Palindrome 的定义是，给定 S, S=S'

KMP 算法的核心是 failure function ，在 currect position 不匹配的情况下，在之前的substring中寻找最长的 suffix 后缀，使得它和 substring 中的 prefix 前缀相同。

Longest Palindromic Substring

考虑到总共可能的 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);
    }
}

Valid Palindrome

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;
    }
}

Palindrome Permutation

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 Permutation II

下面的代码是一个比较粗暴的第一版本，因为要返回所有正确解，属于一个搜索问题。根据 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;
        }
    }
}

[重点] Shortest Palindrome

这题在 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. 关于这个问题，Yu's Garden 的帖子讲的非常赞，推荐一读。

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;
    }

}