2.LeetCode#5 Longest Palindromic Substring

题目描述

求给定字符串的最长回文子串

动态规划求解

可以创建一个数组记录由i开始到j的子串是否是回文子串
满足关系：
dp[i][j] = true ((j - i <= 3 && S[i] == S[j]) || i == j)
dp[i][j] = dp[i+1][j - 1] and S[i] == S[j](j - i > 3)
现在我们可以判断字符串任意两个位置是否是回文串，在遍历一遍找出最长的即可
代码如下(借鉴)：

public static String longestPalindrome(String s) {
        if(s.length() == 0 || s == null){
            return s;
        }
        int len = s.length();
        int maxLen = 0;
        String res = null;

        boolean[][] dp = new boolean[len][len];
        for(int i = len - 1;i >= 0;i--){
            for(int j = i;j < len;j++){
                dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i+1][j-1] == true);//（1）当前遍历到的子串i~j是否是回文子串取决于i+1~j-1，也就是i~j中间的子串是否是回文并且s[i]是否等于s[j]；（2）dp[i][j]是为true则意味着i~j是回文子串，则在下面判断后对res进行更新；如果为false，则该子串不是回文子串，开始遍历下一个子串。

                if(dp[i][j] == true && (res == null || j - i + 1 > maxLen)){//如果该子串长度更长，则更新res
                    res = s.substring(i, j+1);
                    maxLen = res.length();
                }
            }
        }
        return res;

    }

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

采用从中心扩散的方法

由于我们注意到回文串是中心对称的，因此可以以每一个字符作为中心出发去找他的最长回文串，与上述动态规划的方法相比，此方法节省了空间。
代码如下：

public static String longestPalindrome(String s){

        int n = s.length();
        if(n <= 1) return s;
        String longest = "";
        String str;
        for(int i = 0; i < n - 1; i++){

            str = findPalindrome(s, i , i);
            if(str.length() > longest.length()){
                longest = str;
            }
            str = findPalindrome(s, i, i+1);
            if(str.length() > longest.length()){
                longest = str;
            }
        }
        return longest;
    }

    public static String findPalindrome(String s, int left, int right){

        int l = left;
        int r = right;
        int n = s.length();
        while(l >= 0 && r < n && s.charAt(l) == s.charAt(r)){
            l--;
            r++;
        }
        return s.substring(l + 1, r);
    }

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