Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

大意就是找出给定字符串的最长回文

我自己的思路如下：典型的DP问题，判断S[i,j]是否是回文，分三种情况
1.如果i==j，那么S[i,j]是回文
2.如果i - j < 2，表示i,j相邻，在这种情况下如果s[i] == s[j]那么S[i,j]是回文
3.如果i,j不相邻,则必须满足s[i] == s[j] && s[i+1][j-1]为回文，则s[i,j]是回文

public String longestPalindrome(String s) {
        if(s == null || s.length() == 0){
            return null;
        }
        /**
         * dp[i][j] == 1 表示是回文，反之则不是
         */
        int[][] dp = new int[s.length()][s.length()];
        /**
         * maxLength记录回文最大长度，给定字符串中可能有多个回文组，如果我们需要筛选最长的那一个
         * ，则需要maxLength在运行时记录当前最长的回文长度
         * left/right用来记录当前最长回文的起止index，最后我们将用他们从给定字符串中截取最后的结果
         */
        int maxLength = 0, left = 0, right = 0;

        for(int i = 0; i < s.length(); i++){
            for(int j = 0; j <= i; j++){
                /**
                 * s[i] == s[j] 判断， j,i分别表示字符串的首尾index
                 */
                if(s.charAt(i) == s.charAt(j)){
                    /**
                     * i - j < 2 满足相邻或者满足dp[i - 1][j + 1]是回文则dp[i][j]是回文
                     */
                    if(i - j < 2 || dp[i - 1][j + 1] == 1){
                        dp[i][j] = 1;
                    }
                }else{
                    /**
                     * 上述情况都不满足，则不是回文
                     */
                    dp[i][j] = 0;
                }
                /**
                 * 如果dp[i][j]是回文
                 * 并且该回文的长度 >= 之前记录的最长回文长度
                 * 则重置left/right/maxLength
                 */
                if(dp[i][j] == 1 && maxLength < i - j + 1){
                    maxLength = i - j + 1;
                    left = j;
                    right = i;
                }
            }
        }
        /**
         * 根据left/right得到结果
         */
        return s.substring(left, right + 1);
    }

双重for循环O(n2)