LeetCode之5题最长回文串

来源：力扣（LeetCode）https://leetcode-cn.com/problems/longest-palindromic-substring

题目

给你一个字符串 s，找到 s 中最长回文子串。

示例1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例2：

输入：s = "aaaa"
输出："aaaa"

测试用例边界：

1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成

Java版

暴力破解

暴力破解就是通过枚举所有的情况，每次都去判断是否是回文串。 如果完全暴力的话会超时，因此下面的算法进行了优化

public String longestPalindrome(String s) {
    if(null==s || s.length()<=1){
        return s;
    }

    String longestStr = s.substring(0, 1);
    for(int i=0; i<s.length(); i++){
        // 最大长度已经超过后面串的长度
        if(s.length()-i<longestStr.length()){
            break;
        }

        // for(int j=i+1; j<=s.length(); j++){
        for(int j=i+longestStr.length()+1; j<=s.length(); j++){
            String str = s.substring(i, j);
            if(isPalindrome(str) && str.length()>longestStr.length()){
                longestStr = str;
            }
        }
    }
    return longestStr;
}
/**
 * 判断是否是回文串（后续算法的优化点）
 */
private boolean isPalindrome(String str){
    int l = 0;
    int r = str.length()-1;
    
    while(l<r){
        if(str.charAt(l)!=str.charAt(r)){
            return false;
        }
        l++;
        r--;
    }
    return true;
}

动态规划

动态规划的规则：从下标l到r是否是回文串的判断依据有如下2种：1.下标l和下标r位置上的字符是否相同；2.下标l+1到r-1是否是回文串。
因为长度为1时肯定是回文串，所以我只需要从长度为2的地方开始。

动态规划方程：dp[l][r] = dp[l+1][r-1] && s[l]==s[r]

时间复杂度为O(n^2)，空间复杂度也为O(n^2)。

public String longestPalindrome(String s) {
    if(null==s || s.length()<2){
        return s;
    }

    char[] arr = s.toCharArray();
    boolean[][] dp = new boolean[arr.length][arr.length];

    for(int i=0; i<arr.length; i++){
        dp[i][i] = true;
    }

    int start = 0;
    int maxLen = 1;

    // 每次子串的长度
    for(int len=2; len<=arr.length; len++){
        for(int l=0; l<arr.length; l++){
            // 计算右边的位置，因为数组下标从0开始，所以需要减1
            int r = l+len-1;
            if(r>=arr.length){
                break;
            }

            if(arr[l]!=arr[r]){
                dp[l][r] = false;
            }else{
                dp[l][r] = r - l < 3 || dp[l + 1][r - 1];
            }

            if(dp[l][r] && r-l+1>maxLen){
                start = l;
                maxLen = r-l+1;
            }
        }
    }
    return s.substring(start, start+maxLen);
}