[LeetCode] 5. 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.

求字符串中的最大回文子串（从左往右和从右往左读一样的子串）。

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

解法1:

　　遍历每个字符，以该字符为中心，往两边扩散寻找回文子串。应注意奇偶情况，比如"bob"是奇数形式的回文，"noon"就是偶数形式的回文，两种形式的回文都要搜索。该算法时间复杂度为O(n²)。

public class Solution {
    public String longestPalindrome(String s) {
        int maxBegin = 0;  // 最大回文子串的起始点
        int maxLength = 0;  // 最大回文子串的长度
        int currLength = 0;  // 以当前字符为中心的回文子串长度
        
        for (int i = 0; i < s.length() - 1; i++) {
            // 以当前字符为中心寻找回文子串
            currLength = searchPalindrome(s, i, i);
            if (currLength > maxLength) {
                maxLength = currLength;
                maxBegin = i - (currLength >> 1);
            }
            // 如果当前字符和下一个字符相同，还应寻找以这两个字符为中心的回文子串
            if (s.charAt(i) == s.charAt(i + 1)) {
                currLength = searchPalindrome(s, i, i + 1);
                if (currLength > maxLength) {
                    maxLength = currLength;
                    maxBegin = i + 1 - (currLength >> 1);
                }
            }
            
        }
        
        if (maxLength == 0)  maxLength = s.length();
        
        return s.substring(maxBegin, maxBegin + maxLength);
    }
    
    public int searchPalindrome(String s, int left, int right) {
        int step = 1;
        while ((left - step >= 0) && (right + step < s.length())) {
            if (s.charAt(left - step) != s.charAt(right + step))
                break;
            step++;
        }
        return right - left + (step << 1) - 1;
    }
}

解法2:

　　此题还可以用动态规划Dynamic Programming来解，我们维护一个二维数组dp，其中dp[i][j]表示字符串区间[i, j]是否为回文串，当i = j时，只有一个字符，肯定是回文串，如果i = j + 1，说明是相邻字符，此时需要判断s[i]是否等于s[j]，如果i和j不相邻，即i - j >= 2时，除了判断s[i]和s[j]相等之外，dp[j + 1][i - 1]若为真，就是回文串，通过以上分析，可以写出递推式如下：

　　　　dp[i, j] = 1 if i == j

　　　　= s[i] == s[j] if j = i + 1

　　　　= s[i] == s[j] && dp[i + 1][j - 1] if j > i + 1

　　判断顺序：s[0][0] —> s[0][1] —> s[1][1] —> s[0][2] —> s[1][2] —> s[2][2] —> s[0][3] —> ....

public class Solution {
    public String longestPalindrome(String s) {
        boolean[][] isPal = new boolean[s.length()][s.length()];
        int left = 0;
        int right = 0;
        
        for (int j = 0; j < s.length(); j++) {
            for (int i = 0; i < j; i++) {
                isPal[i][j] = (s.charAt(i) == s.charAt(j)) && (j - i < 2 || isPal[i + 1][j - 1]);
                if (isPal[i][j] && (j - i > right - left)) {
                    left = i;
                    right = j;
                }
            }
            isPal[j][j] = true;
        }
        
        return s.substring(left, right + 1);
    }
}

解法3:

　　最后要来的就是大名鼎鼎的马拉车算法Manacher's Algorithm，这个算法的神奇之处在于将时间复杂度提升到了O(n)这种逆天的地步，而算法本身也设计的很巧妙，很值得掌握，具体算法参见：Manacher算法总结和 Manacher's Algorithm 马拉车算法。

public class Solution {
    public String longestPalindrome(String s) {
        
        // 字符串穿插"#"，同时加头加尾防止越界
        StringBuilder sb = new StringBuilder("@#");
        for (int i = 0; i < s.length(); i++) {
            sb.append(s.charAt(i)).append("#");
        }
        sb.append("$");
        
        int[] len = new int[sb.length()];
        int maxCenter = 0;  // 记录最大回文子串的中心位置
        int maxLength = 0;  // 记录最大回文子串的半径
        int id = 0;  // 记录当前计算过的右边界所属的回文子串中心
        int mx = 0;  // 记录当前计算过的右边界
        
        for (int i = 1; i < sb.length() - 1; i++) {
            len[i] = i < mx ? Math.min(len[2 * id - i], mx - i + 1) : 1;
            while (sb.charAt(i - len[i]) == sb.charAt(i + len[i]))
                len[i]++;
                
            if (mx < i + len[i] - 1) {
                mx = i + len[i] - 1;
                id = i;
            }
            if (maxLength < len[i]) {
                maxLength = len[i];
                maxCenter = i;
            }
        }
        return s.substring((maxCenter - maxLength) / 2, (maxCenter - maxLength) / 2 + maxLength - 1);
    }
}