Longest Palindromic Substring

描述​

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.

分析​

f[i][j] = if (i == j) S[i]          if (S[i] == S[j] && f[i+1][j-1] == S[i+1][j-1]) S[i][j]          else max(f[i+1][j-1], f[i][j-1], f[i+1][j])

$f(i,j)=\begin{cases} true & ,i=j\\ S[i]=S[j] & , j = i + 1 \\ S[i]=S[j] \text{ and } f(i+1, j-1) & , j > i + 1 \end{cases}$

备忘录法​

// Longest Palindromic Substring// 备忘录法，会超时// 时间复杂度O(n^2)，空间复杂度O(n^2)public class Solution {    private final HashMap<Pair, String> cache = new HashMap<>();    public String longestPalindrome(final String s) {        cache.clear();        return cachedLongestPalindrome(s, 0, s.length() - 1);    }    String longestPalindrome(final String s, int i, int j) {        final int length = j - i + 1;        if (length < 2) return s.substring(i, j + 1);        final String s1 = cachedLongestPalindrome(s, i + 1, j - 1);        if (s1.length() == length - 2 && s.charAt(i + 1) == s.charAt(j - 1))            return s.substring(i, j + 1);        final String s2 = cachedLongestPalindrome(s, i + 1, j);        final String s3 = cachedLongestPalindrome(s, i, j - 1);        // return max(s1, s2, s3)        if (s1.length() > s2.length()) return s1.length() > s3.length() ? s1 : s3;        else return s2.length() > s3.length() ? s2 : s3;    }    String cachedLongestPalindrome(final String s, int i, int j) {        final Pair key = new Pair(i, j);        if (cache.containsKey(key)) {            return cache.get(key);        } else {            final String result = longestPalindrome(s, i, j);            cache.put(key, result);            return result;        }    }    // immutable    static class Pair {        private int x;        private int y;        public Pair(int x, int y) {            this.x = x;            this.y = y;        }        @Override        public int hashCode() {            return x * 31 + y;        }        @Override        public boolean equals(Object other) {            if (this == other) return true;            if (this.hashCode() != other.hashCode()) return false;            if (!(other instanceof Pair)) return false;            final Pair o = (Pair) other;            return this.x == o.x && this.y == o.y;        }    }}

动规​

// Longest Palindromic Substring// 动规，时间复杂度O(n^2)，空间复杂度O(n^2)class Solution {    public String longestPalindrome(final String s) {        final int n = s.length();        final boolean[][] f = new boolean[n][n];        int maxLen = 1, start = 0;  // 最长回文子串的长度，起点        for (int i = 0; i < n; i++) {            f[i][i] = true;            for (int j = 0; j < i; j++) {  // [j, i]                f[j][i] = (s.charAt(j) == s.charAt(i) &&                        (i - j < 2 || f[j + 1][i - 1]));                if (f[j][i] && maxLen < (i - j + 1)) {                    maxLen = i - j + 1;                    start = j;                }            }        }        return s.substring(start, start + maxLen);    }}

Manacher’s Algorithm​

// Longest Palindromic Substring// Manacher’s Algorithm// 时间复杂度O(n)，空间复杂度O(n)class Solution {    // Transform S into T.    // For example, S = "abba", T = "^#a#b#b#a#$". // ^ and$ signs are sentinels appended to each end to avoid bounds checking    public String preProcess(final String s) {        int n = s.length();        if (n == 0) return "^$"; StringBuilder ret = new StringBuilder("^"); for (int i = 0; i < n; i++) ret.append("#" + s.charAt(i)); ret.append("#$");        return ret.toString();    }    String longestPalindrome(String s) {        String T = preProcess(s);        final int n = T.length();        // 以T[i]为中心，向左/右扩张的长度，不包含T[i]自己，        // 因此 P[i]是源字符串中回文串的长度        int[] P = new int[n];        int C = 0, R = 0;        for (int i = 1; i < n - 1; i++) {            int iMirror = 2 * C - i; // equals to i' = C - (i-C)            P[i] = (R > i) ? Math.min(R - i, P[iMirror]) : 0;            // Attempt to expand palindrome centered at i            while (T.charAt(i + 1 + P[i]) == T.charAt(i - 1 - P[i]))                P[i]++;            // If palindrome centered at i expand past R,            // adjust center based on expanded palindrome.            if (i + P[i] > R) {                C = i;                R = i + P[i];            }        }        // Find the maximum element in P.        int maxLen = 0;        int centerIndex = 0;        for (int i = 1; i < n - 1; i++) {            if (P[i] > maxLen) {                maxLen = P[i];                centerIndex = i;            }        }        final int start =(centerIndex - 1 - maxLen) / 2;        return s.substring(start, start + maxLen);    }}