最长回文子串

对于一个子串而言,如果它是回文串,并且长度大于 2,那么将它首尾的两个相同的字母去除之后,它仍然是个回文串。所以状态转移方程为dp[i][j] = (dp[i+1][j-1]) && chars[i]==chars[j];同时对于j-1>=i+1 所以 j-i+1(数组长度)>=3,l=j-1>=2。
那么当l=0时,为字符本身,肯定为回文串。
当l=1时需要判断左右字符是否相等
这里使用位移量l作为循环变量,是为了防止出现dp[i][j]中j<i这种不合理的情况发生。所以使用j=i+l来代替 forj。第二个循环里使用i来代表下标,从0开始往后遍历,需要注意的是,由于j=i+l,而j的下标也是一定小于数组长度的,所以i+l<length;

//给你一个字符串 s,找到 s 中最长的回文子串。 
//
// 
//
// 示例 1: 
//
// 
//输入:s = "babad"
//输出:"bab"
//解释:"aba" 同样是符合题意的答案。
// 
//
// 示例 2: 
//
// 
//输入:s = "cbbd"
//输出:"bb"
// 
//
// 示例 3: 
//
// 
//输入:s = "a"
//输出:"a"
// 
//
// 示例 4: 
//
// 
//输入:s = "ac"
//输出:"a"
// 
//
// 
//
// 提示: 
//
// 
// 1 <= s.length <= 1000 
// s 仅由数字和英文字母(大写和/或小写)组成 
// 
// Related Topics 字符串 动态规划 
// 👍 3258 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    //暴力求解
    public String longestPalindrome(String s) {
        if(s.length()<=1) {
            return s;
        }
        char[] chars = s.toCharArray();
        //记录回文字符串的最大长度,最小为1,即单个字符可以构成一个回文字符串
        int maxLen = 1;
        //记录回文字符串的起始下标
        int start = 0;
        //从下标为0的开始查找回文字符串
        for (int i = 0; i < s.length() - 1; i++) {
            for (int j = i+1; j < s.length() ; j++) {
                //如果回文字符串长度大于最大长度,则记录
                if(j-i+1 > maxLen && checkPalindromeString(chars,i,j)) {
                    maxLen = j-i+1;
                    start = i;
                }
            }
        }
        return String.copyValueOf(chars,start,maxLen);
    }

    /**
     * 校验字符串是否是回文字符串
     * @param chars
     * @param i
     * @param j
     * @return
     */
    public  boolean checkPalindromeString(char[] chars, int i, int j) {
        while (i<j) {
            //回文字符串一定是左右相等的
            if (chars[i] != chars[j]) {
                return false;
            }else {
                ++i;
                --j;
            }
        }
        return true;
    }
    //动态规划
    public String longestPalindrome(String s) {

        char[] chars = s.toCharArray();
        if(chars.length<=1) {
            return s;
        }
        String ans = "";
        boolean[][] palindrome = new boolean[chars.length][chars.length];
        //l代表回文字符串的位移量
        for (int l = 0; l < chars.length; l++) {
            for (int i = 0; i+l < chars.length; i++) {
                //j代表区间最右的下标
                int j = i+l;
                if(l == 0) {
                    palindrome[i][j] = true;
                }else if(l == 1){
                    palindrome[i][j] = (chars[i] == chars[j]);
                }else {
                    //对于一个回文字符串,如果它的长度大于2,那么把他的首尾两个字符分别去掉后(两个字符也必须相等).剩下的字符串仍为回文字符串.
                    //所以状态转移方程为dp[i][j] = dp[i+1][j-1] && chars[i]==chars[j]
                    //在这个方程组需要保证(j-1)-(i+1)>=0 ,所以j-i >= 2 即j-i+1>=3 回文字符串的长度需要大于等于3
                    //当回文字符串的长度=1时,为字符,肯定为回文串为true
                    //当回文字符串的长度=2时,需要判断左右字符是否相等
                    palindrome[i][j] = ((chars[i] == chars[j]) && palindrome[i+1][j-1]);
                }

                if(palindrome[i][j] && l+1 > ans.length()) {
                    ans = String.copyValueOf(chars, i, l+1);
                }
            }
        }
        return ans;
    }

}
//leetcode submit region end(Prohibit modification and deletion)