力扣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個小時還不會，改天一定補上/補上啦