数据结构与算法题解（11）：最长回文子串

给定字符串S，求它的最长回文子串。假设S的最长长度为1000，并且仅有唯一的最长回文子串。

一、暴力法（ Brute Force）

最简便，但同时时间复杂度也是最高的肯定是暴力解法，就是遍历字符串的“所有子串”，并判断每个子串是否为对称回文。因为字符串所有子串的复杂度为$O(n^2)$，在判断回文，总体的复杂度达到$O(n^3)$。

• 复杂度：时间 $O(n^3) $空间 $O(1)$
  可以做一些简单的优化：

• 从最长的子串开始遍历，一旦找到一个回文，就终止迭代。

• 判断回文采用收缩法，从最外一对字符往中心推进。

public class Solution {
    public String longestPalindrome(String s) {
        for (int size = s.length(); size > 0; size--) {
            for (int low = 0, high = low+size-1; high < s.length(); low++, high++) {
                if (shrinkCheckPalindrome(s,low,high)) {
                    return s.substring(low,high+1);
                }
            }
        }
        return s.substring(0,1);
    }
    public boolean shrinkCheckPalindrome(String s, int low, int high) {
        while (low <= high) {
            if (s.charAt(low) == s.charAt(high)) {
                low++; high--;
            } else {
                return false;
            }
        }
        return true;
    }
}

二、动态规划

根据回文的特性，一个大回文按比例缩小后的字符串也必定是回文，比如ABCCBA，那BCCB肯定也是回文。所以我们可以根据动态规划的两个特点：第一大问题拆解为小问题，第二重复利用之前的计算结果，来解答这道题。那如何划分小问题呢，我们可以先把所有长度最短为1的子字符串计算出来，根据起始位置从左向右，这些必定是回文。然后计算所有长度为2的子字符串，再根据起始位置从左向右。到长度为3的时候，我们就可以利用上次的计算结果：如果中心对称的短字符串不是回文，那长字符串也不是，如果短字符串是回文，那就要看长字符串两头是否一样。这样，一直到长度最大的子字符串，我们就把整个字符串集穷举完了，但是由于使用动态规划，使计算时间从$O(N^3)$减少到$O(n^2)$。

• 复杂度：时间 $O(n^2) $空间 $O(n^2)$

class Solution {
    public String longestPalindrome(String s) {
      int n = s.length();
      String res = null;
      boolean[][] dp = new boolean[n][n];
      for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
          dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1]);
          if (dp[i][j] && (res == null || j - i + 1 > res.length())) {
            res = s.substring(i, j + 1);
          }
        }
      }
      return res;
    }
}

三、中心扩散法

动态规划虽然优化了时间，但也浪费了空间。实际上我们并不需要一直存储所有子字符串的回文情况，我们需要知道的只是中心对称的较小一层是否是回文。所以如果我们从小到大连续以某点为个中心的所有子字符串进行计算，就能省略这个空间。 这种解法中，外层循环遍历的是子字符串的中心点，内层循环则是从中心扩散，一旦不是回文就不再计算其他以此为中心的较大的字符串。由于中心对称有两种情况，一是奇数个字母以某个字母对称，而是偶数个字母以两个字母中间为对称，所以我们要分别计算这两种对称情况。

• 复杂度：时间 O(n^2) 空间 O(1)

public class Solution {
    private int max = 0;
    private String res = "";
    public String longestPalindrome(String s) {
        if (s.length() == 1) { return s; }
        for (int i = 0; i < s.length()-1; i++) {
            checkPalindromeExpand(s,i,i);
            checkPalindromeExpand(s,i,i+1);
        }
        return res;
    }
    public void checkPalindromeExpand(String s, int low, int high) {
        while (low >= 0 && high < s.length()) {
            if (s.charAt(low) == s.charAt(high)) {
                if (high - low + 1 > max) {
                    max = high - low + 1;
                    res = s.substring(low,high+1);
                }
                low--; high++;
            } else {
                return;
            }
        }
    }
}

四、马拉车算法

public class Solution {
    public String longestPalindrome(String s) {
        if(s.length()<=1){
            return s;
        }
        // 预处理字符串，避免奇偶问题
        String str = preProcess(s);
        // idx是当前能够向右延伸的最远的回文串中心点，随着迭代而更新
        // max是当前最长回文串在总字符串中所能延伸到的最右端的位置
        // maxIdx是当前已知的最长回文串中心点
        // maxSpan是当前已知的最长回文串向左或向右能延伸的长度
        int idx = 0, max = 0;
        int maxIdx = 0;
        int maxSpan = 0;
        int[] p = new int[str.length()];
        for(int curr = 1; curr < str.length(); curr++){
            // 找出当前下标相对于idx的对称点
            int symmetryOfCurr = 2 * idx - curr;
            // 如果当前已知延伸的最右端大于当前下标，我们可以用对称点的P值，否则记为1等待检查
            p[curr] = max > curr? Math.min(p[symmetryOfCurr], max - curr):1;
            // 检查并更新当前下标为中心的回文串最远延伸的长度
            while((curr+p[curr])<str.length() && str.charAt(curr+p[curr])==str.charAt(curr-p[curr])){
                p[curr]++;
            }
            // 检查并更新当前已知能够延伸最远的回文串信息
            if(curr+p[curr]>max){
                max = p[curr] + curr;
                idx = curr;
            }
            // 检查并更新当前已知的最长回文串信息
            if(p[curr]>maxSpan){
                maxSpan = p[curr];
                maxIdx = curr;
            }
        }
        //去除占位符
        return s.substring((maxIdx-maxSpan)/2,(maxSpan+maxIdx)/2-1);
    }
    
    // 预处理，如ABC,变为$#A#B#C#
    private String preProcess(String s){
        
        StringBuilder sb = new StringBuilder();
        sb.append("$");
        for(int i = 0; i < s.length(); i++){
            sb.append("#");
            sb.append(s.charAt(i));
        }
        sb.append("#");
        return sb.toString();
    }
}