LeetCode.5-最长回文子串(Longest Palindromic Substring)

这是悦乐书的第342次更新，第366篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Medium级别的第3题（顺位题号是5）。给定一个字符串s，找到s中最长的回文子字符串。您可以假设s的最大长度为1000。例如：

输入：“babad”

输出：“bab”

注意：“aba”也是一个有效的答案。

输入：“cbbd”

输出：“bb”

02 第一种解法

暴力解法。

使用两层循环截取出所有的子串，判断该子串是否是回文，从中取长度最长的子串作为结果输出。

此解法时间复杂度是O(N^3)，空间复杂度是O(1)。

public String longestPalindrome(String s) {

    int max = 0, n = s.length();

    String result = "";

    for (int i=0; i<n; i++) {

        for (int j=i+1; j<=n; j++) {

            String tem = s.substring(i,j);

            if (isPalindrome(tem)) {

                if (j-i > max) {

                    max = j-i;

                    result = tem;

                }

            }

        }

    }

    return result;

}

public boolean isPalindrome(String s){

    int left = 0, right = s.length()-1;

    while (left < right) {

        if (s.charAt(left) != s.charAt(right)) {

            return false;

        }

        left++;

        right--;

    }

    return true;

}

03 第二种解法

我们也可以换一种找回文的方式，从左右两边向中间变成由中间向左右两边。

此时需要考虑回文的长度是奇数还是偶数的情况，如果是奇数形回文，就以当前字符为中心左右两边寻找，例如回文"bab"；如果是偶数形回文，需要两个字符，并且这两个字符是相等的，则需要以当前字符和其相邻的字符为中心向左右两边寻找，例如回文"abba"。

此解法的时间复杂度是O(N^2)，空间复杂度是O(1)。

public String longestPalindrome2(String s) {

    if (s.length() < 2) {

        return s;

    }

    int n = s.length(), start = 0, end = 0;

    for (int i=0; i<n-1; i++) {

        int len = helper(s, i, i);

        int len2 = helper(s, i, i+1);

        int len3 = Math.max(len, len2);

        if (len3 > end - start) {

            start = i - (len3-1)/2;

            end = i + len3/2;

        }

    }

    return s.substring(start, end+1);

}

/**

 * 以当前字符为中心向左右两边扩散，寻找回文子串

 * @param s 字符串

 * @param left 起始索引

 * @param right 结束索引

 * @return 回文子串长度

 */

public int helper(String s, int left, int right) {

    int n = s.length(), L = left, R = right;

    while (L >= 0 && R < n && s.charAt(L) == s.charAt(R)) {

        // 继续向左寻找

        L--;

        // 继续向右寻找

        R++;

    }

    return R - L -1;

}

04 第三种解法

动态规划算法，用空间换时间，是对第一种解法的改进。

此解法的时间复杂度是O(N^2)，空间复杂度是O(N^2)。

public String longestPalindrome3(String s) {

        if (s.length() < 2) {

            return s;

        }

        int n = s.length(), start = 0, end = 0;

        int maxLen = 0;

        // dp[j][i]表示子串[j,i]是回文

        boolean[][] dp = new boolean[n][n];

        // 右边界

        for (int i=0; i<n; i++) {

            // 左边界

            for (int j=i; j>=0; j--) {

                if (i == j) {

                    dp[j][i] = true;

                } else if (s.charAt(i) == s.charAt(j)) {

                    // 回文中至少3个字符

                    if (j < i-1) {

                        dp[j][i] = dp[j+1][i-1];

                    } else {

                        dp[j][i] = true;

                    }

                } else {

                    dp[i][j] = false;

                }

                // 比较最大值，并重新赋值

                if (i-j+1 > maxLen && dp[j][i]) {

                    maxLen = i-j+1;

                    start = j;

                    end = i;

                }

            }

        }

        return s.substring(start, end+1);

    }

05 第四种解法

马拉车算法(Manacher's Algorithm)，来自于讨论区，这是第一次听说这种算法，将时间复杂度降低到了O(N)，也是很厉害了，后续抽时间来详细了解下这个算法。

public String longestPalindrome4(String s) {

    String T = preProcess(s);

    int n = T.length();

    int[] P = new int[n];

    int C = 0, R = 0;

    for (int i = 1; i < n - 1; i++) {

        int i_mirror = 2 * C - i;

        if (R > i) {

            P[i] = Math.min(R - i, P[i_mirror]);

        } else {

            P[i] = 0;

        }

        while (T.charAt(i + 1 + P[i]) == T.charAt(i - 1 - P[i])) {

            P[i]++;

        }

        if (i + P[i] > R) {

            C = i;

            R = i + P[i];

        }

    }

    int maxLen = 0;

    int centerIndex = 0;

    for (int i = 1; i < n - 1; i++) {

        if (P[i] > maxLen) {

            maxLen = P[i];

            centerIndex = i;

        }

    }

    int start = (centerIndex - maxLen) / 2;

    return s.substring(start, start + maxLen);

}

/**

 *

 * @param s

 * @return

 */

public String preProcess(String s) {

    int n = s.length();

    if (n == 0) {

        return "^$";

    }

    String ret = "^";

    for (int i = 0; i < n; i++) {

        ret += "#" + s.charAt(i);

    }

    ret += "#$";

    return ret;

}

06 小结

算法专题目前已连续日更超过六个月，算法题文章211+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。

以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！

巴特西