手写代码：求一个字符串最长回文子串

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param s string字符串 
     * @return string字符串
     */
    string longestPalindrome(string s)
    {
        int n = s.size();
        if(n < 2)
            return s;
        //dp[i][j] 表示s[i...j]为回文
        vector<vector<int>> dp(n,vector<int>(n,true));
        int maxLen = 1,begin = 1;
                //从2开始，也就是从s为2的长度开始
        for(int L = 2; L < n; ++L)
            for(int i = 0;i < n; ++i)
            {
                int j = L + i -1;  //找右边界
                if(j > n)
                    break;
                if(s[i] != s[j])
                    dp[i][j] = false;
                else
                {
                    if(j - i < 3)
                        dp[i][j] = true;
                    else
                        dp[i][j] = dp[i+1][j-1];
                }
                                //如果i..j为回文串且长度比maxLen大，则更新
                if(dp[i][j] && j-i+1 > maxLen)
                {
                    maxLen = j-i+1;
                    begin = i;
                }
            }
        return s.substr(begin,maxLen);
        
    }
};

class Solution {
public:
    string longestPalindrome(string s) {
        int start = 0,end = 0,maxdistance = 1,n = s.length();
        vector<vector<bool> >   isPalindroem(n,vector<bool>(n,false));
        for(int i = 0;i < n;i++){
            isPalindroem[i][i] = true;
            if(i != n-1 && s[i] == s[i+1]){
                isPalindroem[i][i+1] = true;
                start = i;
                end = i+1;
                maxdistance = 2;
            }
        }
    
        for(int i = n-3;i >= 0;i--)
            for(int j = i+2;j < n;j++){
                isPalindroem[i][j] = isPalindroem[i+1][j-1] && s[i] == s[j];
                if(isPalindroem[i][j] && j-i + 1 > maxdistance){
                    start = i;
                    end = j;
                    maxdistance = j-i+1;
                }
            }

        return s.substr(start,maxdistance);
    }
};

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