LeetCode 5. Longest Palindromic

2016-11-28 本文已影响125人 stevewang

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example:
Input: "cbbd"
Output: "bb"

大致意思就是给定一个字符串s，找到s中最长回文子串。
回文的含义是：正着看和倒着看相同，如abba和abcba.
子串的含义是：在原串中连续出现的字符串片段。
这是一道经典的算法题，在《算法竞赛入门经典》以及2016腾讯实习生校招笔试题中都曾遇到过，之前的文章中也曾解决过一个更复杂的问题。
解决该问题最方便的方法是中心扩展法，从中心向两边扩展回文串，需要注意的是，回文串有两种形式：长度为奇数的回文串（形如abcba）以及长度为偶数的回文串（形如abba）.
使用这种方法寻找最长回文子串的时间复杂度为O(n^2)，空间复杂度为O(1)。
代码如下：

public class Solution {
    public String longestPalindrome(String s) {

        int n = s.length();
        int start = 0, maxLen = 0;
        for (int i = 0; i < n; i++) {   // 以i为中心向两边扩展
            for (int j = 0; i - j >= 0 && i + j < n; j++) { // 长度为奇数的回文串（形如abcba）
                if (s.charAt(i - j) != s.charAt(i + j)) {
                    break;
                }
                if (2 * j + 1 > maxLen) {
                    maxLen = 2 * j + 1;
                    start = i - j;
                }
            }
            for (int j = 0; i - j >= 0 && i + 1 + j < n; j++) { // 长度为偶数的回文串（形如abba），中心点(两个b)位置分别为i和i+1，向两边扩展范围(i-j,i+1+j)
                if (s.charAt(i - j) != s.charAt(i + 1 + j)) {
                    break;
                }
                if (2 * j + 2 > maxLen) {
                    maxLen = 2 * j + 2;
                    start = i - j;
                }
            }
        }
        return s.substring(start, start + maxLen);
    }
}

此外，解决该问题还可以使用Manacher算法（中文名马拉车算法），它可以在O(N)的时间复杂度内得到一个字符串中以每一个字符为中心的最长回文子串。而对于长度为偶数的回文串，比如abba，可以通过插入未出现过的特殊字符#，从而转化成长度为奇数的回文串#a#b#b#a#
该算法的基本原理就是利用已知回文串的左半部分来推导右半部分。
用数组p[i]表示以i为中心的最长回文子串半径长度，从前向后扫描字符串s中的每一个字符计算出它们对应的p[i]，找到最大的p[i]即找到了s的最长回文子串。
在从前向后扫描的过程中，需要计算p[i]时一定已经计算好了p[1]....p[i-1]，假设现在扫描到了i+k这个位置，需要计算p[i+k]
定义max是以i+k之前的字符为中心的所有回文串所能延伸到的最远的位置（回文右边界），假设这个字符的位置是i，即max = i + p[i];// i为i+k之前到达最远的回文串中心
这时i+k的位置分布有两种情况：

i+k这个位置不在前面的任何回文串内部（不含max点），即 i+k >= max，这时初始化p[i+k] = 0;//本身是回文串
然后p[i+k]左右延伸，即while(s.charAt(i+k - p[i+k]) == s.charAt(i+k + p[i+k])) p[i+k]++；
i+k这个位置被前面以i为中心的回文串包含，即 i+k < max，这样的话p[i+k]就不是从0开始了

对于第二种情况，根据回文串的性质，可知i+k这个位置的字符关于i与i-k对称，这时p[i+k]又要分为以下三种情况来计算（黑色是以i为中心的回文串范围，绿色是以i-k为中心的回文串范围）

2.1

如上图，若以i-k为中心的回文串有一部分在以i为中心的回文串范围之外（绿色的左端在黑色范围之外），则以i+k为中心的回文串范围一定是橙色部分，有 p[i+k] = max - (i+k) = i + p[i] - i - k = p[i] - k，即 p[i+k] = Math.min(p[i-k], p[i]-k);（p[i] - k < p[i-k]）

如果小于橙色部分，则违反了与i-k关于i的对称性
假设超出橙色部分，如图中的紫色延长线c和d，根据以i为中心的回文子串性质，b部分与c部分相对于i对称；同理根据以i-k为中心的回文子串性质，b部分与a部分相对于i-k对称，最终得出a部分与d部分相对于i位置对称，超出了以i为中心的回文子串（黑色）范围，假设不成立。

2.2

如上图，若以i-k为中心的回文串全部在以i为中心的回文串范围内且未达到左侧边界（左侧绿色在黑色范围之内），则以i+k为中心的回文串范围一定是右侧绿色部分，有p[i+k] = p[i-k]，即 p[i+k] = Math.min(p[i-k], p[i]-k);（p[i-k] < p[i] - k）

如果小于右侧绿色部分，同样是违反了与i-k关于i的对称性
假设超出右侧绿色部分，如图中的紫色延长线c和d，根据以i为中心的回文子串性质，b部分与c部分相对于i对称，a部分与d部分也相对于i对称，最终得出a部分与b部分相对于i-k位置对称，超出了以i-k为中心的回文子串（左侧绿色）范围，假设不成立。

2.3

如上图，若以i-k为中心的回文串全部在以i为中心的回文串范围内且恰好达到左侧边界（左侧绿色到达黑色范围左边界），则有 i-k - p[i-k] = i - p[i]，即 p[i-k] = p[i] - k
以i+k为中心的回文串范围一定包含右侧绿色部分，并有可能超出（如图橙色部分），这时初始化 p[i+k] = Math.min(p[i-k], p[i]-k);（p[i-k] = p[i] - k），并向外延伸while(s.charAt(i+k - p[i+k]) == s.charAt(i+k + p[i+k])) p[i+k]++；

综合上面所有情况，总结出核心代码：

p[i+k] = 0;
if(i+k < max) {
    p[i+k] = Math.min(p[i-k], p[i]-k);
}  
while(s.charAt(i+k - p[i+k]) == s.charAt(i+k + p[i+k])) {
    p[i+k]++;
}

上面分析中把当前的字符定义在位置i+k，配合i及i-k这种对称的命名方式是为了便于我们理解，在实际编程中当前字符的位置通常为i，最长延伸回文串的中心点通常定义成id（id < i），则i关于id的对称位置为id - (i - id) = 2 * id - i，把上面的思想带入到实际编程中：

在遍历到位置为i的字符时，已知以位置为id的字符为中心的回文串已延伸到的最远位置max = id + p[id]，如果当前字符在这个回文串中，我们就要赋值 p[i] = Math.min(p[2 * id - i], max - i)，即以当前位置i关于id的对称位置2 * id - i为中心的回文串半径与该对称位置距离最长延展回文串左边界长度max - i二者间的较小值。代码如下：

public class Solution {
    public String longestPalindrome(String s) {

        String t = "#";
        for (int i = 0; i < s.length(); i++) { // 插入#，统一转化为长度为奇数的回文串
            t += s.charAt(i) + "#";
        }
        int[] p = new int[t.length()];       // p[i]表示以i为中心的最长回文子串半径长度
        int maxP = 0, maxC = 0;              // 数组p中的最大值，最长回文子串的中心点
        int id = 0;                          // 当前位置之前已到达最远的回文串中心
        int max = id + p[id];                // 当前查找位置之前，已知能影响最右边的串
        for (int i = 0; i < t.length(); i++) {
            if (i < max) {                   // 当前字符在之前最远回文串的范围之内
                p[i] = Math.min(p[2 * id - i], max - i);
            }
            while (i - p[i] >= 0 && i + p[i] < t.length() && t.charAt(i - p[i]) == t.charAt(i + p[i])) {
                p[i]++;
            }
            if (i + p[i] > max) {   // 更新最远回文串
                id = i;
                max = id + p[id];
            }
            if (p[i] > maxP) {      // 保留最大值信息
                maxP = p[i];
                maxC = i;
            }
        }
        if (t.charAt(maxC) == '#') { // 还原长度为偶数的回文串
            return s.substring((maxC - 2) / 2 - (maxP - 2) / 2, (maxC - 2) / 2 + 1 + (maxP - 2) / 2 + 1);
        } else {                     // 还原长度为奇数的回文串
            return s.substring((maxC - 1) / 2 - (maxP - 1) / 2, (maxC - 1) / 2 + (maxP - 1) / 2 + 1);
        }
    }
}

总体来说，Manacher算法还是比较复杂的，不会有人要求你在45分钟的coding session中去实现它，大致了解即可。

LeetCode 5. Longest Palindromic

猜你喜欢

热点阅读