动态规划-leetcode5. 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.

二、解决思路
思路一：暴力法，先求出字符串的全部子字符串，然后对每个子字符串进行判断，O(n^3)
思路二：动态规划法，可以发现字符串存在一些规律，f(i, j) = f(i - 1, j + 1)，当且仅当i - 1和 j + 1字符相同（其中i、j为字符串索引下标），思路一在对每个子字符串进行判断时，未保存之前判断的信息，因此可以用空间换时间的思想，使用二维数组保存之前判断信息，时空O(n^2)
思路二扩展：思路二算法实现使用了数组保存的是最长回文子字符串，该思路使用二维数组存储下标起止子字符串是否回文字符串，并使用两变量动态求出最长回文子字符串
思路三：参考solution方法1，问题是求回文字符，只需求字符串与其翻转字符串的公共最长子字符串（非常巧妙，根据字符串特征着手），但在求最长子字符串过程中，还需要判断，时空O(n^2)
思路四：思路二使用了 O(n^2) 空间消耗，还是从回文字符串特点入手，回文字符串左右对称，因此，可以以一个字符为中心，从左右两边进行判断是否相等，求出最长子字符串，O(n^2)
思路五：参考solution的Manacher's Algorithm，马拉车算法的核心就两点：

• 对原字符串进行预处理，使字符串变为奇数长度
• 还是根据回文字符串特点，定义一个一维数组P，用于存放以该字符为中心的回文最长长度，假设下标C的回文最长长度为R（P[C] = R），下标 i 关于C的对称下标为 i_mirror, i 和 i_mirror有如下关系：P[i] = P[i_mirror]，但有三种情况不满足上述关系：
  1）i_mirror达到字符串左边界
  2）P[i_mirror] 超出了C回文范围
  3）i 等于R
  这三种情况需要通过左右扩展进行计算

三、算法实现
思路二

public String longestPalindrome(String s) {
        int lens = s.length();
        if (lens == 0 || lens == 1) return s;
        int[][] arr = new int[lens][lens];
        String res = "";
        for (int i = 0; i < lens; i++) {
            arr[i][i] = 1;
            res = chackMaxStr(s, res, arr, i, i);
            res = getLongStr(s, res, arr, i - 1, i + 1, lens);
            //System.out.println(res);
            if((i + 1) < lens) {
                if (s.charAt(i) == s.charAt(i + 1)) {
                    arr[i][i + 1] = 2;
                    // 需要特殊处理
                    res = chackMaxStr(s, res, arr, i, i + 1);
                    res = getLongStr(s, res, arr, i - 1, i + 2, lens);
                } else {
                    arr[i][i + 1] = 1;
                    // 需要特殊处理
                    res = chackMaxStr(s, res, arr, i, i + 1);
                    res = getLongStr(s, res, arr, i, i + 2, lens);
                }
                //System.out.println(res);
            }
        }
        //printArr(arr);
        return res;
    }

    public String chackMaxStr(String s, String cur, int[][] arr, int i, int j){
        String res = cur;
        int max = cur.length();
        if(arr[i][j] > max){
            res = s.substring(i, j + 1);
        }
        return res;
    }

    public String getLongStr(String s, String cur, int[][] arr, int i, int j, int lens){
        String res = cur;
        int max = res.length();
        while(i >= 0 && j < lens){
            if(s.charAt(i) == s.charAt(j)){
                arr[i][j] = arr[i + 1][j - 1] + 2;
                if(arr[i][j] > max){
                    //System.out.println(i + " = " + j + ", " + s.substring(i, j + 1));
                    res = s.substring(i, j + 1);
                    max = arr[i][j];
                }
            } else {
                break;
            }
            i--;
            j++;
        }
        return res;
    }

思路二扩展

public String longestPalindrome(String s) {
        int lens = s.length();
        if (lens == 0 || lens == 1) return s;
        int start = 0;
        int len = 1;
        // 数组用于标识下标起止子字符串是否回文字符
        int[][] arr = new int[lens][lens];
        for(int i = 0; i < lens; i++){
            arr[i][i] = 1;
            if((i + 1) < lens){
                if(s.charAt(i) == s.charAt(i + 1)){
                    start = i;
                    arr[i][i + 1] = 1;
                    len = 2;
                }
            }
        }
        // 动态求出最长回文子串
        for(int i = 3; i <= lens; i++){
            for(int j = 0; j <= lens - i; j++){
                if(s.charAt(j) == s.charAt(j + i - 1) && (arr[j + 1][j + i - 2] == 1)){
                    arr[j][j + i - 1] = arr[j + 1][j + i - 2];
                    start = j;
                    len = i;
                }
            }
        }
        //System.out.println(start + " = " + len);
        String res = s.substring(start, start + len);
        return res;
    }

思路四

public String longestPalindrome(String s) {
        int lens = s.length();
        if (lens == 0 || lens == 1) return s;
        String res = s.substring(0, 1);
        int i = 1;
        String tmp = "";
        String tmp1 = "";
        while(i < lens){
            // 判断该字符是否与前字符相同, 分两种情况分别处理
            if(s.charAt(i) == s.charAt(i - 1)){
                tmp = checkLeftRightStr(i, i, lens, s);
                tmp1 = checkLeftRightStr(i - 1, i, lens, s);
            } else {
                tmp = checkLeftRightStr(i, i, lens, s);
            }
            res = tmp.length() > res.length() ? tmp : res;
            res = tmp1.length() > res.length() ? tmp1 : res;
            i++;
        }
        return res;
    }

    public String checkLeftRightStr(int i, int j, int lens, String s){
        String res = s.substring(i, j + 1);
        i--;
        j++;
        //System.out.println(i + " = " + j);
        while(i >= 0 && j < lens){
            if(s.charAt(i) == s.charAt(j)){
                res = s.substring(i, j + 1);
            } else {
                break;
            }
            i--;
            j++;
            //System.out.println(i + " = " + j);
        }
        return res;
    }

思路五

public String longestPalindrome(String s) {
        int lens = s.length();
        if (lens == 0 || lens == 1) return s;
        // 字符预处理
        StringBuilder sb = new StringBuilder();
        sb.append('#');
        for(int i = 0; i < lens; i++){
            sb.append(s.charAt(i));
            sb.append('#');
        }
        String s1 = sb.toString();
        //System.out.println(s1);
        lens = s1.length();
        // 回文中心下标
        int c = 0;
        // 最长回文长度
        int max = 0;
        int mc = 0;
        // 回文右边界
        int r = 0;
        int[] arr = new int[lens];
        for(int i = 0; i < lens; i++){
            arr[i] = i < r ? Math.min(arr[2 * c - i], r - i) : 1;
            while((i + arr[i] < lens) && (i - arr[i] >= 0) &&
                    (s1.charAt(i + arr[i]) == s1.charAt(i - arr[i]))){
                arr[i] += 1;
            }
            if(r < (i + arr[i] - 1)){
                r = i + arr[i] - 1;
                c = i;
            }
            if(max < arr[i]){
                max = arr[i] - 1;
                mc = i;
            }
        }
        //System.out.println(c + " = " + r + " = " + mc + " = " + max);
        String res = s1.substring(mc - max + 1, mc + max);
        res = res.replaceAll("#", "");
        return res;
    }