Palindrome 问题

Longest Palindromic Substring

middle-out 由每个字符作为起点，往两边扫。

Palindrome 长度可能是奇数，也可能是偶数。所以指定 seed 往两边扩展的时候要注意先把 start / end 指针推到“不是 seed” 的位置上。

public class Solution {
    public String longestPalindrome(String s) {
        if(s == null || s.length() <= 1) return s;
        if(s.length() == 2) {
            if(s.charAt(0) == s.charAt(1)) return s;
            else return s.substring(1);
        }

        int maxLen = 1;
        int maxStart = 0, maxEnd = 0;

        for(int i = 0; i < s.length(); i++) {
            // the palindrome length could be even or odd, so we need put the pointer on postion which is not seed
            int left = i - 1;
            while(left >= 0 && s.charAt(left) == s.charAt(i)) left--;

            int right = i + 1;
            while(right < s.length() && s.charAt(right) == s.charAt(i)) right++;

            while(left >= 0 && right < s.length()) {
                if(s.charAt(left) == s.charAt(right)) {
                    left--;
                    right++;
                } else {
                    break;
                }
            }
            // update the longest 
            if(right - end - 1 > maxLen) {
                maxLen = right - end - 1;
                maxStart = left + 1;
                maxEnd = right - 1;
            }
        }

        return s.substring(maxStart, maxEnd + 1);
    }
}

方法二：思路基本一样，就是写法上有一点不同 基本思路是对于每个子串的中心（可以是一个字符，或者是两个字符的间隙，比如串abc,中心可以是a,b,c,或者是ab的间隙，bc的间隙）往两边同时进行扫描，直到不是回文串为止。

public class Solution {
    public String longestPalindrome(String s) {
        if(s == null || s.length() == 0) return s;

        String result = "";
        int max = 1;

        // we go over the center point of each substring, it could be a char 
        // or a gap bewtween two char
        for(int i = 0; i < 2 * s.length() - 1; i++) {
            // middle out
            int left = i / 2;
            int right = i / 2;
            // in the gap
            if(i % 2 == 1) {
                right++;
            }

            String str = getPalindrome(s, left, right);

            if(str.length() > max) {
                result = str;
                max = str.length();
            }
        }

        return result;
    }

    public String getPalindrome(String s, int i, int j) {
        while(i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
            i--;
            j++;
        }
        return s.substring(i + 1, j);
    }
}

时间复杂度:O(n^2)

Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

把s都变成小写，跳过非alphanumeric 的字符

public class Solution {
    public boolean isPalindrome(String s) {
        if(s == null || s.length() < 2) 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)) return false;

            start++;
            end--;
        }
        return true;
    }
}

(Snapchat) Make Palindrome

给一个string，算出把他变成palindrome的最少操作数。操作包括，增加，删减以及修改。

思路： 既然是找最小操作数，那么肯定是用动归的方法。 因为是palindrome，我们可以考虑用区间型动归。

dp[i][j] 表示从i到j的substring变成palindrome 需要的最小操作数

初始化对角线

转移方程： dp[i][j] = if (s[i] == [j]) dp[i+1][j - 1], else Math.min(dp[i][j-1], dp[i + 1][j]) + 1

问题：修改，增加和删除有什么不同？