05.最长回文子串

问题引入：

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1： 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。

示例 2： 输入: "cbbd" 输出: "bb"

1. 方法一：暴力法

思路：列举所有的子串，找到最长的回文串

时间复杂度：O(n^3),两次for循环，判断是否回文还有一次for循环

空间复杂度：O(1)

public String longestPalindrome1(String s) {
        String ans = "";
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j <= s.length(); j++) {
                String test = s.substring(i, j);
                if (isPalindrome(test) && test.length() > ans.length()) {
                    ans = test;
                }
            }
        }
        return ans;
    }

    public boolean isPalindrome(String test) {
        for (int i = 0; i < test.length() / 2; i++) {
            if (test.charAt(i) != test.charAt(test.length() - 1 - i)) {
                return false;
            }
        }
        return true;
    }

2. 方法二：中心扩展算法

思路：先找到中心点，然后分别向左右两边检测，直到遍历完所有的中心点，找到最大的回文字符字串 中心点共有2n-1个，其中有两种情况， 一种子串是奇数个字符，中心点为中间的数， 另一种是子串有偶数个字符，中间点就是中间两个数间的间隙 所以，n个数，n-1个间隙，总共2n-1个中心点

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

    public String longestPalindrome3(String s) {
        if (s == null || s.length() == 0)
            return "";
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = nowLongest(s, i, i);
            int len2 = nowLongest(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    public int nowLongest(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(right) == s.charAt(left)) {
            left--;
            right++;
        }
        return right - left - 1;
    }

3. 方法三：最长公共子串

算法思路：我们可以根据回文串的特点，左右对称的特点，我们可以再定义一个字符串存放原字符串的倒置字符串reverse,然后比较两个字符串找到最长公共子串，该公共子串就是该字符串的最长回文串。

但是，会有特殊情况，比如abc123cba，他的倒置字符串是abc123cba，最长公共子串为abc（或cba），

我们会发现并不是正确答案，所以我们的算法还需要加个判断条件， 我们需要判断倒置前的下标是否和倒置后的下标匹配，即是否是同一位置的元素。

找到一个字符倒置前的下标很简单，比如该字符下标为j，那么before = length - 1 - j;

比如我们用i指向原字符串子串的末尾字符，用j指向倒置字符串子串的末尾字符， j倒置前的位置下标before_j = length - 1 - j；

如果before_ j + maxson.len -1 == i，那么说明它就是我们要找的回文串。

分析完思路，我们再来看看最长公共子串如何求解？ 这个有很多种方法，我们就有动态规划法解决。

思路：

• 申请一个二维的数组arr[len][len]，把每个元素初始化为0。
• 写个双重循环遍历二维数组，其中i表示原字符串s的下标，j表示倒置字符串reverse的下标.
• 然后判断对应的字符是否相等，及判断s.charAt(i)==reverse.charAt(j) 相等的话， arr[i][j] =arr[i-1][j-1] + 1。
• 其中i=0或j=0的情况单独分析，如果字符相等的话直接赋值arr[i][j]=1.

• 最后arr[i][j]里面就是保存着公共子串的长度，该公共子串就是以i结尾的，我们用

  就可以找到子串开始的下标，

• 再截取原字符串就可以得到最长公共子序列。

时间复杂度：O(n^2) 两层for循环

空间复杂度：O(n^2) 一个二维数组

    public String longestPalindrome4(String s) {
        if (s.equals(""))
            return "";
        String reverse = new StringBuffer(s).reverse().toString();
        int len = s.length();
        int[][] arr = new int[len][len];     //arr[i][j] 存放着公共子串的长度
        int maxlen = 0, maxEnd = 0;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if(s.charAt(i) == reverse.charAt(j)) {
                    if( i == 0 || j == 0) {
                        arr[i][j] = 1;
                    }
                    else {
                        arr[i][j] = arr[i-1][j-1]+1;
                    }
                }
                if(arr[i][j] > maxlen) {
                    //j是当前倒置字符串的子串的末尾下标，i是当前原子串的末尾下标，before是j在原字符串对应下标
                    int before = len - 1 - j;    
                    
                    //判断字符下标是否对应
                    if(before + arr[i][j] - 1 == i) {
                        maxlen = arr[i][j];     
                        maxEnd = i;       //i为当前子串的末尾字符
                    }
                    
                }
            }
        }
        //substring(i,j)截取从下标i到j-1的子串
        return s.substring(maxEnd - maxlen + 1,maxEnd +1); 
    }

4. 方法四：优化后的最长公共子串

特点：可以将空间复杂度降至O(n)

思路：

我们发现上述的动态规划法，用二维数组，其实每次都是一列一列更新，

* i = 1,j=0,1,2,3……

* i = 2,j=0,1,2,3……

* i = 3,j=0,1,2,3……

* ……………

我们每次更新数据，用到的公式arr[i][j] = arr[i-1][j-1]+1;

发现，其实只需要前一列的信息，更新第三列的时候，只用到第二列的数据，第一列就没有用了，

所以我们用一个一维数组就可以了，arr[j]代表当前列的元素的最长公共子串长度

但是更新每一列的时候，我们会用到这一列上一个元素的值，比如arr[i] = arr[i-1]+1

所以，在遍历j的时候不能从0到len-1，而是从len-1到0遍历。

public String longestPalindrome5(String s) {
        if (s.equals(""))
            return "";
        
        String reverse = new StringBuffer(s).reverse().toString();
        int length = s.length();
        int[] arr = new int[length];
        int maxLen = 0;
        int maxEnd = 0;
        for (int i = 0; i < length; i++)
            /************** 修改的地方 ***************************/
            for (int j = length - 1; j >= 0; j--) {
                /**************************************************/
                if (s.charAt(i) == reverse.charAt(j)) {
                    if (i == 0 || j == 0) {
                        arr[j] = 1;
                    } else {
                        arr[j] = arr[j - 1] + 1;
                    }
                    /************** 修改的地方 ***************************/
                    // 之前二维数组，每次用的是不同的列，所以不用置 0 。
                } else {
                    arr[j] = 0;
                }
                /**************************************************/
                if (arr[j] > maxLen) {
                    int beforeRev = length - 1 - j;
                    if (beforeRev + arr[j] - 1 == i) {
                        maxLen = arr[j];
                        maxEnd = i;
                    }

                }
            }
        return s.substring(maxEnd - maxLen + 1, maxEnd + 1);
    }