最长回文子串

题目

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

代码

暴力匹配

• 时间复杂度 O(N^3)
• 空间复杂度 O(1)

    public String longestPalindrome(String str) {
        int n = str.length();
        if (n < 2) {
            return str;
        }
        int maxLen = 1;
        int begin = 0;
        char[] charArray = str.toCharArray();
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (j - i + 1 > maxLen && validPalindromic(charArray, i, j)) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return str.substring(begin, begin + maxLen);
    }

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

动态规划

• 时间复杂度 O(N^2)
• 空间复杂度 O(N^2)

    public String longestPalindrome(String str) {
        int n = str.length();
        if (n < 2) {
            return str;
        }
        int maxLen = 1;
        int begin = 0;
        char[] charArray = str.toCharArray();
        boolean[][] dp = new boolean[n][n];
        for (int i = 0; i < n; i++)
            dp[i][i] = true;
        for (int j = 1; j < n; j++) {
            for (int i = 0; i < j; i++) {
                if (charArray[i] != charArray[j])
                    dp[i][j] = false;
                else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return str.substring(begin, begin + maxLen);
    }

中心扩散法

• 时间复杂度 O(N^2)
• 空间复杂度 O(1)

    public String longestPalindrome(String str) {
        int n = str.length();
        if (n < 2) {
            return str;
        }
        int maxLen = 1;
        String res = str.substring(0, 1);
        for (int i = 0; i < n - 1; i++) {
            String oddStr = centerSpread(str, i, i);
            String evenStr = centerSpread(str, i, i + 1);
            String maxLenStr = oddStr.length() > evenStr.length() ? oddStr : evenStr;
            if (maxLenStr.length() > maxLen) {
                maxLen = maxLenStr.length();
                res = maxLenStr;
            }
        }
        return res;
    }

    private String centerSpread(String s, int left, int right) {
        int len = s.length();
        int i = left, j = right;
        while (i >= 0 && j < len) {
            if (s.charAt(i) == s.charAt(j)) {
                i--;
                j++;
            } else {
                break;
            }
        }
        return s.substring(i + 1, j);
    }

中心扩散法的改进

    public String longestPalindrome(String str) {
        if (str == null || str.length() < 1) return "";
        if (str.length() == 1) return str;
        int[] range = new int[2];
        char[] arr = str.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            i = findLongest(arr, i, range);
        }
        return str.substring(range[0], range[1] + 1);
    }

    private int findLongest(char[] str, int low, int[] range) {
        int high = low;
        while (high < str.length - 1 && str[high + 1] == str[low])
            high++;
        int ans = high;
        while (low > 0 && high < str.length - 1 && str[low - 1] == str[high + 1]) {
            low--;
            high++;
        }
        if (high - low > range[1] - range[0]) {
            range[0] = low;
            range[1] = high;
        }
        return ans;
    }