题目描述

Longest Palindromic Substring

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000, 且只包含字母和数字

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

Input: s = "cbbd"
Output: "bb"

Input: s = "a"
Output: "a"
Example 4:

Input: s = "ac"
Output: "a"

From leetcode No.5 Medium (opens new window)

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

解法

暴力循环

class Solution {
    public String longestPalindrome(String s) {
        if (s.length() < 2) {
            return s;
        }
        int max = 1;
        int begin = 0;
        char[] arr = s.toCharArray();
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {

                if (j - i + 1 > max && isPalindrome(arr, i, j)) {
                    max = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + max);
    }

    private boolean isPalindrome(char[] s, int left, int right) {
        while (left < right) {
            if (s[left] != s[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

动态规划

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        String ans = "";
        for (int n = 0; n < len; n++) {
            for (int i = 0; i + n < len; i++) {
                int j = i + n;
                if (n == 0) { // i==j, dp[i][j] == true
                    dp[i][j] = true;
                } else if (n == 1) { //j = i +1
                    dp[i][j] = (s.charAt(i) == s.charAt(j));
                } else { // j -i > 2
                    dp[i][j] = (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]);
                }
                if (dp[i][j] && n + 1 > ans.length()) {
                    ans = s.substring(i, j + 1);
                }
            }
        }
        return ans;
    }
}

中心扩散法

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    public int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            --left;
            ++right;
        }
        return right - left - 1;
    }
}

中心扩散法优化

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        int start = 0;
        int end = 0;
        Character[] arr = new Character[2 * len + 1];
        for (int i = 0; i < arr.length; i++) {
            if (i % 2 == 0) {
                arr[i] = '#';
            } else {
                arr[i] = s.charAt(i / 2);
            }
        }
        for (int i = 0; i < arr.length; i++) {
            int ret = this.expandAroundCenter(arr, i);
            if (ret > end - start) {
                start = i - (ret - 1) / 2;
                end = i + ret / 2;
            }
        }
        if (start % 2 == 0) {
            start = start / 2;
        } else {
            start = (start - 1) / 2;
        }
        if (end % 2 == 0) {
            end = end / 2 - 1;
        } else {
            end = (end - 1) / 2 - 1;
        }
        return s.substring(start, end + 1);
    }

    public int expandAroundCenter(Character[] s, int center) {
        int left = center - 1;
        int right = center + 1;
        while (left >= 0 && right < s.length && s[left] == s[right]) {
            --left;
            ++right;
        }
        return right - left - 1;
    }
}

总结

1. 暴力循环
   • 最容易想到的解法，遍历所有子串，判断是否为回文串，是的话记录字符串长度和起始索引
   • 大概有 n*n个子串，每个平均长度为 n/2, 时间复杂度为 n³
2. 动态规划
   • 假设字符串 s长度为 n, 以一个二维数组 f[i][j](i >= 0, j >= i, j <= n-1) 的布尔值来表示索引 i, i+1, ...j的字符串是否为回文串
   • 如果 f[i][j] 为 true，那么 f[i+1][j-1] 肯定为 true，且 s[i] == s[j]
     • 这里的前提条件是 j>2
   • 特殊的边界条件为 n == 1 或 n == 2
     • f[i][j] 永远为 true (i == j)
     • n == 2， 如果 s[i] == s[j], 则 f[i][j]为 true (j - i = 1)
   • 状态转移方程的推导
     • 字符串 s长度为 1， f[i][j] 永远为 true， 此时最长回文串长度为 1
     • 字符串 s长度为 2， f[i][j]，判断 s[i] == s[j]， 如果为 true，此时最长回文串长度为 2
     • 字符串 s长度大于 2， f[i][j]，判断 f[i+1][j-1] && s[i] === s[j]， 如果为 true，此时最长回文串长度为 j-i+1
   • 求最长回文字符串，即 f[i][j] 为 true的前提下，j-i+1为最大值的情况, 得到字符串子串 s[i, j]
3. 中心扩散法
   • 思想是把当前字符串中的每个元素及每两个元素当作中心，向两边扩散，直到到达边界或不满足回文串的条件
   • 满足回文串条件则记录起点和终点，比较长度即可得到最长回文子串
   • 相比动态规范，该算法降低了空间复杂度
   • 由于回文串的组成，决定了它可能有 1或 2个中心，也可以先将每个字符的前后空隙均填充相同的(原字符串中不存在的)特殊字符
     • eg：#, 这样 n个字符加上 n+1个空隙，就组成了 2n+1固定的奇数个字符的新字符串
     • 新字符串就只可能存在一个中心，可进一步降低时间复杂度
4. manacher 算法
   • refer to manacher-ago

参考

longest-palindromic-substring (opens new window)