5. Longest Palindromic Substring

题目描述和难度

  • 题目描述:

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。

示例 1:

输入: "babad"

输出: "bab"

注意: "aba"也是一个有效答案。

示例 2:

输入: "cbbd"

输出: "bb"

思路分析

求解关键:

思路1:中心扩散法:枚举回文串的中心(注意分回文串是奇数还是偶数时候的判断,可以同一设计一个方法),得到回文串,从中统计中最长的回文串即可。

思路2:动态规划方法。

思路3:专门解决回文串的一个著名算法 Manacher 算法。

参考解答

参考解答1:中心扩散法

public class Solution {

    public String longestPalindrome(String s) {
        int len = s.length();
        if (len == 0) {
            return "";
        }
        int longestPalindrome = 1;
        String longestPalindromeStr = s.substring(0, 1);
        for (int i = 0; i < len; i++) {
            String palindromeOdd = centerSpread(s, len, i, i);
            String palindromeEven = centerSpread(s, len, i, i + 1);
            String maxLen = palindromeOdd.length() > palindromeEven.length() ? palindromeOdd : palindromeEven;
            if (maxLen.length() > longestPalindrome) {
                longestPalindrome = maxLen.length();
                longestPalindromeStr = maxLen;
            }
        }
        return longestPalindromeStr;
    }

    private String centerSpread(String s, int len, int left, int right) {
        int l = left;
        int r = right;
        while (l >= 0 && r < len && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        // 这里要特别小心,跳出 while 循环的时候,是第 1 个满足 s.charAt(l) != s.charAt(r) 的时候
        // 所以,不能取 l,不能取 r
        return s.substring(l + 1, r);
    }
}

参考解答2:动态规划

public class Solution2 {

    public String longestPalindrome(String s) {
        int len = s.length();
        if (len == 0) {
            return "";
        }
        int longestPalindrome = 1;
        String longestPalindromeStr = s.substring(0, 1);
        boolean[][] dp = new boolean[len][len];
        // abcdedcba
        //   j   i
        // 如果 dp[j,i] = true 那么 dp[j+1,i-1] 也一定为 true
        // [j+1,i-1] 一定要构成至少两个元素额区间( 1 个元素的区间,s.charAt(i)==s.charAt(j) 已经判断过了)
        // 即 j+1 < i-1,即 i > j + 2 (不能取等号,取到等号,就退化成 1 个元素的情况了)
        // 应该反过来写
        for (int i = 0; i < len; i++) {
            for (int j = 0; j <= i; j++) {
                // 区间应该慢慢放大
                if (s.charAt(i) == s.charAt(j) && (i <= j + 2 || dp[j + 1][i - 1])) {
                    // 写成 dp[j][i] 就大错特错了,不要顺手写习惯了
                    dp[j][i] = true;
                    if (i - j + 1 > longestPalindrome) {
                        longestPalindrome = i - j + 1;
                        longestPalindromeStr = s.substring(j, i + 1);
                    }
                }
            }
        }
        return longestPalindromeStr;
    }
}

参考解答3:使用 Manacher 算法

/**
 * 使用 Manacher 算法
 */
public class Solution3 {

    /**
     * 创建分隔符分割的字符串
     *
     * @param s      原始字符串
     * @param divide 分隔字符
     * @return 使用分隔字符处理以后得到的字符串
     */
    private String generateSDivided(String s, char divide) {
        int len = s.length();
        if (len == 0) {
            return "";
        }
        if (s.indexOf(divide) != -1) {
            throw new IllegalArgumentException("参数错误,您传递的分割字符,在输入字符串中存在!");
        }
        StringBuilder sBuilder = new StringBuilder();
        sBuilder.append(divide);
        for (int i = 0; i < len; i++) {
            sBuilder.append(s.charAt(i));
            sBuilder.append(divide);
        }
        return sBuilder.toString();
    }

    public String longestPalindrome(String s) {
        int len = s.length();
        if (len == 0) {
            return "";
        }
        String sDivided = generateSDivided(s, '#');
        int slen = sDivided.length();
        int[] p = new int[slen];
        int mx = 0;
        // id 是由 mx 决定的,所以不用初始化,只要声明就可以了
        int id = 0;
        int longestPalindrome = 1;
        String longestPalindromeStr = s.substring(0, 1);
        for (int i = 0; i < slen; i++) {
            if (i < mx) {
                // 这一步是 Manacher 算法的关键所在,一定要结合图形来理解
                // 这一行代码是关键,可以把两种分类讨论的情况合并
                p[i] = Integer.min(p[2 * id - i], mx - i);
            } else {
                // 走到这里,只可能是因为 i = mx
                if (i > mx) {
                    throw new IllegalArgumentException("程序出错!");
                }
                p[i] = 1;
            }
            while (i - p[i] >= 0 && i + p[i] < slen && sDivided.charAt(i - p[i]) == sDivided.charAt(i + p[i])) {
                p[i]++;
            }
            // 我们想象 mx 的定义,它是遍历过的 i 的 i + p[i] 的最大者
            // 写到这里,我们发现,如果 mx 的值越大,
            // 进入上面 i < mx 的判断的可能性就越大,这样就可以重复利用之前判断过的回文信息了
            if (i + p[i] > mx) {
                mx = i + p[i];
                id = i;
            }

            if (p[i] - 1 > longestPalindrome) {
                longestPalindrome = p[i] - 1;
                longestPalindromeStr = sDivided.substring(i - p[i] + 1, i + p[i]).replace("#", "");
            }
        }
        return longestPalindromeStr;
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0005-longest-palindromic-substring ,如果我的题解有错误,或者您有更好的解法,欢迎您告诉我 liweiwei1419@gmail.com