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.

分析

最长回文子串，非常经典的题。

思路一：暴力枚举，以每个元素为中间元素，同时从左右出发，复杂度O(n^2)。

思路二：记忆化搜索，复杂度O(n^2)。设f[i][j] 表示[i,j]之间的最长回文子串，递推方程如下：

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

思路三：动规，复杂度O(n^2)。设状态为f(i,j)，表示区间[i,j]是否为回文串，则状态转移方程为

f(i,j)={true,i=jS[i]=S[j],j=i+1S[i]=S[j] and f(i+1,j−1),j>i+1f(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}

思路四：Manacher’s Algorithm, 复杂度O(n)。详细解释见 http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html。

备忘录法

  1. // Longest Palindromic Substring
  2. // 备忘录法，会超时
  3. // 时间复杂度O(n^2)，空间复杂度O(n^2)
  4. public class Solution {
  5.     private final HashMap<Pair, String> cache = new HashMap<>();
  7.     public String longestPalindrome(final String s) {
  8.         cache.clear();
  9.         return cachedLongestPalindrome(s, 0, s.length() - 1);
  10.     }
  12.     String longestPalindrome(final String s, int i, int j) {
  13.         final int length = j - i + 1;
  14.         if (length < 2) return s.substring(i, j + 1);
  16.         final String s1 = cachedLongestPalindrome(s, i + 1, j - 1);
  18.         if (s1.length() == length - 2 && s.charAt(i + 1) == s.charAt(j - 1))
  19.             return s.substring(i, j + 1);
  21.         final String s2 = cachedLongestPalindrome(s, i + 1, j);
  22.         final String s3 = cachedLongestPalindrome(s, i, j - 1);
  24.         // return max(s1, s2, s3)
  25.         if (s1.length() > s2.length()) return s1.length() > s3.length() ? s1 : s3;
  26.         else return s2.length() > s3.length() ? s2 : s3;
  27.     }
  29.     String cachedLongestPalindrome(final String s, int i, int j) {
  30.         final Pair key = new Pair(i, j);
  32.         if (cache.containsKey(key)) {
  33.             return cache.get(key);
  34.         } else {
  35.             final String result = longestPalindrome(s, i, j);
  36.             cache.put(key, result);
  37.             return result;
  38.         }
  39.     }
  41.     // immutable
  42.     static class Pair {
  43.         private int x;
  44.         private int y;
  46.         public Pair(int x, int y) {
  47.             this.x = x;
  48.             this.y = y;
  49.         }
  51.         @Override
  52.         public int hashCode() {
  53.             return x * 31 + y;
  54.         }
  56.         @Override
  57.         public boolean equals(Object other) {
  58.             if (this == other) return true;
  59.             if (this.hashCode() != other.hashCode()) return false;
  60.             if (!(other instanceof Pair)) return false;
  62.             final Pair o = (Pair) other;
  63.             return this.x == o.x && this.y == o.y;
  64.         }
  65.     }
  66. }

动规

  1. // Longest Palindromic Substring
  2. // 动规，时间复杂度O(n^2)，空间复杂度O(n^2)
  3. class Solution {
  4.     public String longestPalindrome(final String s) {
  5.         final int n = s.length();
  6.         final boolean[][] f = new boolean[n][n];
  7.         int maxLen = 1, start = 0;  // 最长回文子串的长度，起点
  9.         for (int i = 0; i < n; i++) {
  10.             f[i][i] = true;
  11.             for (int j = 0; j < i; j++) {  // [j, i]
  12.                 f[j][i] = (s.charAt(j) == s.charAt(i) && 
  13.                         (i - j < 2 || f[j + 1][i - 1]));
  14.                 if (f[j][i] && maxLen < (i - j + 1)) {
  15.                     maxLen = i - j + 1;
  16.                     start = j;
  17.                 }
  18.             }
  19.         }
  20.         return s.substring(start, start + maxLen);
  21.     }
  22. }

Manacher’s Algorithm

  1. // Longest Palindromic Substring
  2. // Manacher’s Algorithm
  3. // 时间复杂度O(n)，空间复杂度O(n)
  4. class Solution {
  5.     // Transform S into T.
  6.     // For example, S = "abba", T = "^#a#b#b#a#$".
  7.     // ^ and $ signs are sentinels appended to each end to avoid bounds checking
  8.     public String preProcess(final String s) {
  9.         int n = s.length();
  10.         if (n == 0) return "^$";
  12.         StringBuilder ret = new StringBuilder("^");
  13.         for (int i = 0; i < n; i++) ret.append("#" + s.charAt(i));
  15.         ret.append("#$");
  16.         return ret.toString();
  17.     }
  19.     String longestPalindrome(String s) {
  20.         String T = preProcess(s);
  21.         final int n = T.length();
  22.         // 以T[i]为中心，向左/右扩张的长度，不包含T[i]自己，
  23.         // 因此 P[i]是源字符串中回文串的长度
  24.         int[] P = new int[n];
  25.         int C = 0, R = 0;
  27.         for (int i = 1; i < n - 1; i++) {
  28.             int iMirror = 2 * C - i; // equals to i' = C - (i-C)
  30.             P[i] = (R > i) ? Math.min(R - i, P[iMirror]) : 0;
  32.             // Attempt to expand palindrome centered at i
  33.             while (T.charAt(i + 1 + P[i]) == T.charAt(i - 1 - P[i]))
  34.                 P[i]++;
  36.             // If palindrome centered at i expand past R,
  37.             // adjust center based on expanded palindrome.
  38.             if (i + P[i] > R) {
  39.                 C = i;
  40.                 R = i + P[i];
  41.             }
  42.         }
  44.         // Find the maximum element in P.
  45.         int maxLen = 0;
  46.         int centerIndex = 0;
  47.         for (int i = 1; i < n - 1; i++) {
  48.             if (P[i] > maxLen) {
  49.                 maxLen = P[i];
  50.                 centerIndex = i;
  51.             }
  52.         }
  54.         final int start =(centerIndex - 1 - maxLen) / 2;
  55.         return s.substring(start, start + maxLen);
  56.     }
  57. }

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/string/longest-palindromic-substring.html