力扣5-最长回文子串

Copyright © Zi10ng

道阻且长

• 题目地址

题目描述

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

示例 1：

输入: “babad”

输出: “bab”

题目思路

• 刚看到这个题的时候，想到了两种做法，一种是O(3)，另外一种是O(2)
• 第一种是从左到右，从右到左，从子串的两边开始遍历每一个子字符串并核对比较，即完全暴力
• 第二种是从左到右，从子串的中间到两边扩展，即中心扩展法

动态规划

之后发现了动态规划算法也可解

给定一个字符串

abcba

dp的过程是：

• 1.先看ab是否是回文串，得

  dp[0][1]==0

• 2.再看abc是否为回文串，得

  dp[0][2]==0

  ，其中需要根据

  d[1][1]==1

• 3.再看abcd是否为回文串，得

  dp[0][3]==0

  ，其中需要根据

  dp[1][2]==0

  ，
• 3.1我们需要注意，在此之前，以经计算出了

  dp[1][3]==1

• 4.再看abcd是否为回文串，得

  dp[0][4]==1

  ，其中需要根据

  dp[1][3]==1

  ，

马拉车

最后一种是针对于回文子串的马拉车算法：

给定一个字符串

abcba

• 先给字符串进行加工：

  #a#b#c#b#a

  ，保证了个数为奇数
• 我们需要知道，设半径为

  r[index]

  ，则以

  index

  为中心的回文子串的长度为

  r[index]-1

• 如果我们已知以

  index=2

  为中心的字符串是回文串，那么我们可以通过性质得知其之后到index为2的回文串结束的回文子串的长度
• 链接1
• 链接2

解法

我的算法①

/**
     * 我的算法，三重循环。好像是叫滑动窗口来着？
     * 第一重从前往后，第二重从后往前，第三重用来判断
     * 增加一个loop和if中的left<=right是为了防止多余循环
     * @param s 给定字符串
     * @return 字符串
     */
    public String longestPalindrome(String s) {

        String longestSubString = "";
        int length = s.length();
        for(int left = 0; left < length; left++){
            LOOP:
            for (int right = length - 1; right >= 0; right --) {
                if (s.charAt(left) == s.charAt(right) && left <= right) {
                    for (int tempLeft = left, tempRight = right; s.charAt(tempLeft) == s.charAt(tempRight); tempLeft ++, tempRight --){
                        if (tempLeft == tempRight || tempLeft + 1 == tempRight){
                            longestSubString = s.substring(left,right + 1).length() > longestSubString.length() ? s.substring(left,right + 1):longestSubString;
                            break LOOP;
                        }
                    }
                }
            }
        }
        return longestSubString;
    }
           

我的算法②

/**
     * 中心扩展法，双重循环
     * @param s 给定字符串
     * @return 返回字符串
     */
    public String centerExpansion(String s){

        String longestSubString = "";
        String centerLongestSubString = "";
        int length = s.length();
        for (int i = 0; i < length; i++) {
            centerLongestSubString = centerExpansionSubString(s,i,i + 1).length() > centerExpansionSubString(s,i,i).length() ? centerExpansionSubString(s,i,i + 1) : centerExpansionSubString(s,i,i);
            longestSubString = longestSubString.length() > centerLongestSubString.length() ? longestSubString : centerLongestSubString;
        }
        return longestSubString;
    }

    /**
     * centerExpansion子算法，但是通过这个超时了
     * 目的是考虑了奇偶性
     * @param s 传入字符串
     * @param left 左边index
     * @param right 右边index
     * @return 字符串
     */
    private String myCenterExpansionSubString(String s, int left, int right){
        String longestSubString = "";
        for (int centerLeft = left, centerRight = right; centerLeft >=0 && centerRight < s.length(); centerLeft--, centerRight++){
            if (s.charAt(centerLeft) == s.charAt(centerRight)){
                longestSubString = s.substring(centerLeft,centerRight + 1).length() > longestSubString.length() ? s.substring(centerLeft,centerRight + 1) : longestSubString;
            }else {
                break;
            }
        }
        return longestSubString;
    }

    /**
     * 更新了myCenterExpansionSubString算法
     * @param s 传入字符串
     * @param left 左边index
     * @param right 右边index
     * @return 字符串
     */
    private String centerExpansionSubString(String s, int left, int right){
        while (left >=0 && right < s.length() && s.charAt(left) == s.charAt(right)){
            left--;
            right++;
        }
        return s.substring(left + 1,right );
    }
           

动态规划

/**
     * 动态规划
     * 一般最优求解都是动态规划找出状态转移方程（二维数组的上三角形式），降低内存可通过滚动数组
     * @param s 给定字符串
     * @return 返回最长子串
     */
    public String dP(String s){
        String longestSubString = "";
        int length = s.length();
        boolean[][] dp = new boolean[length][length];
        for (int right = 0; right < length; right++) {
            for (int left = 0; left <= right; left ++){
                if (s.charAt(right) == s.charAt(left) && (right - left <= 2 || dp[left + 1][right - 1])){
                    dp[left][right] = true;
                    longestSubString = right - left + 1 > longestSubString.length() ? s.substring(left, right + 1) : longestSubString;
                }
            }
        }
        return longestSubString;
    }
           

马拉车

/**
     * 马拉车算法，可以结合KMP一块看，专用于解决回文子串，o(1)
     * @param s 给定字符串
     * @return 回文子串
     */
    public String manacher(String s) {
        String longestSubString = "";
        //对s进行加工使其变成奇数个
        StringBuilder stringBuilder = new StringBuilder("#");
        for (int i = 0; i < s.length(); i++) {
            stringBuilder.append(s.charAt(i)).append("#");
        }

        int length = stringBuilder.length();
        //定义半径
        int[] r = new int[length];
        //定义mid和mid+r
        int mid = 0, max = 0;
        for (int i = 0; i < length; i++) {
            if (i < max){
                r[i] = Integer.min(max - i, r[mid * 2 - i]);
            }else {
                r[i] = 1;
            }
            //上边的if是马拉车的精髓，即通过abadabaxx中的d的半径计算出倒数第二个b的半径，但是它只能计算出b的半径是2
            //下面的while循环就是计算出b的半径可能会大于2，如abadabada，此时b的半径是4
            while (i - r[i] >= 0 && i + r[i] < length && stringBuilder.charAt(i + r[i]) == stringBuilder.charAt(i - r[i])){
                r[i] ++;
            }
            //接下来该更新max和mid的值了
            if (max < i + r[i]){
                max = i +r[i];
                mid = i;
            }
            if (longestSubString.length() < r[i] - 1){
                longestSubString = stringBuilder.substring(i - r[i] + 1, i + r[i]).replace("#", "");
                System.out.println(longestSubString);
            }
        }
        return longestSubString;
    }
           

感悟

• 一般求最优解都可用到DP，二维数组的上三角，如果优化内存可用到滚动数组
• 马拉车有点难理解，看了1个小时还不会，改天一定补上/补上啦