聊聊演算法——迴文字元串

2020 年 9 月 6 日
筆記

我這天天寫核心業務的人，都沒用什麼演算法啊！其實演算法無處不在，棧隊列樹鏈表都包含演算法思想，演算法並不是單純指用程式碼解決那些深奧難懂的數學邏輯問題，而是程式碼中的普適化思維。並且演算法也不可怕，是基本功，就像足球中的體能訓練，微軟Google，想不想去？他們都是用演算法來伺候上門人的，所以還是別太片面地看待問題。演算法也是非常講究的，稍有破綻，失之千里。熟悉各種框架各種源碼，不如下筆寫演算法！因為框架是「用」，演算法是「想」。今天來分析下迴文字元串的解法。

「準備」

Idea2019.03/Gradle6.0.1/Maven3.6.3/JDK11.0.4

「難度」 新手–戰士–老兵–大師

「目標」

1.查找字元串的最長迴文子串演算法

1 需求

找迴文是很常見的一種場景，所以拿來做個典型。所謂迴文，即左右對稱的字元串，如「ABCBA」，它有三種解法，我這裡只說兩種：「中心擴展法」和「動態規劃」，還有個Manacher 演算法，此文略！

2 中心擴展法

「思路：既然迴文是對稱的，肯定有個中心，如從中心開始向兩個方向同步擴展，直到遇到不同字元，即為最長迴文子串。」

程式碼(Java版)：

public class N005 {
    public static void main(String[] args) {
        String s = "DECCED";
        System.out.println(sub(s));
    }
    /** 中心擴展 因擴展有兩種可能 一是ABA型 二是ABBA型，故可以寫一個公用的擴展函數expand()*/
    private static String sub(String s){
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            // ABBA型
            int len1 = expand(s,i,i + 1);
            // ABA型
            int len2 = expand(s,i,i );
            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);
    }

    private static int expand(String s,int left,int right){
        int l = left;
        int r = right;
        while (l >= 0 && r < s.length() && s.charAt(l)==s.charAt(r)){
            l--;
            r++;
        }
        return r - l - 1;
    }
}

以上程式碼解析：

迴文對稱有兩種，一是」ABA」型，另一種是」ABBA」型，for循環中將字元串每個字元都假設為對稱中心，使用兩種類型的假設來左右擴展，並保存最大迴文資訊；
為啥獨立出來一個expand函數？因為對稱有兩種類型，寫個函數來複用，程式碼更簡潔；
expand函數的作用是獲得迴文的長度，比如」ABA」返回3，」ABBA」則返回4 ，兩個下標差再減去 1 ，要注意的細節是這兩個指針的最終位置，如下圖，」ABA」型(上)，」ABBA」型如 (上)：

關於程式碼中start和end 變數的計算：

start=i-(len-1)/2，考慮上面兩種類型的情況，按上面圖例來說，i=2，start結果為 0 和 -0.5，但 (int) 0 和 (int) -0.5 都等於 0 ；
end=i+len/2，同理，按上面圖例來說，i=2，end結果為 4.5 和 5，(int) 4.5 和 (int) 5 等於 4 和 5 ；

使用這樣的寫法，雖然有點繞，主要是綜合了兩種類型的可能結果，分開寫也可有其他形式。

最後的細節就是subString方法，「ABCDE」.subString(0,5) 輸出才是「ABCDE」。

3 動態規劃法

我在前篇文章已經專門聊了「動態規劃」，雖然動態規劃嚴格講是用於解決階段決策問題的，但其核心思想(類似數學歸納法)也可用於其他場景，使用的就是狀態轉移方程。動態規劃一定會使用dpTable來記錄中間結果。

「思路：如果一個字元串是迴文串，那麼去掉首尾字元的子串也肯定是迴文串，反過來想，如果子串 sub[i+1,j-1] 是迴文串，只需要看 i 和 j 位置的字元是否相同，即可判斷sub[i,j] 是否屬於迴文串。」

因為有 i 和 j ，我們使用一個二維數組做dpTable，如果定義dp[i][j]為位置 i 到 j的子串(包含首尾字元)是否為迴文串，按照思路即可寫出狀態轉移方程(Λ意為and)：

dp[i][j] = dp[i+1][j-1] Λ (char[i] == char[j])

那麼這個dpTable 的對角線都是 true，因為 i = j 時，只有單個字元，同時，因為是從i 到 j 的子串，可以肯定 i < j，故只需計算dpTable右上部分：

於是可以先寫一個初始版本(Java)：

private String sub2(String s){
    int len = s.length();
    boolean[][] dp = new boolean[len][len];
    // 初始化dp表的部分值
    for (int i = 0; i < len; i++) {
        dp[i][i] = true;
    }
    //
    for (int j = 1; j < len; j++) {
        for (int i = 0; i < j; i++) {
            if (s.charAt(i) != s.charAt(j)){
                dp[i][j] = false;
            }else {
                dp[i][j] = dp[i + 1][j - 1];
            }
        }
    }
    // 記錄迴文串的開始位置和長度
    int start = 0;
    int length = 0;
    return s.substring(start,length);
}

再考慮邊界情況，在char[i] == char[j] 時：

即子串subStr(i+1,j-1)長度無法構成子串，長度小於2，(j-1)-(i-1)+1<2，簡化為 j-i<3 ，等價於subStr(i,j)長度為 2 或 3：

如果子串subStr(i+1,j-1)是空，那麼subStr(i,j)是迴文串；
如果子串subStr(i+1,j-1)只有一個字元，顯然一個字元是迴文串，那麼subStr(i,j)是迴文串；

補充邊界後：

private static String sub2(String s){
    int len = s.length();
    boolean[][] dp = new boolean[len][len];
    // 記錄迴文串的開始位置和長度
    int start = 0;
    int length = 0;
    // 初始化dp表的部分值
    for (int i = 0; i < len; i++) {
        dp[i][i] = true;
    }
    //
    for (int j = 1; j < len; j++) {
        for (int i = 0; i < j; i++) {
            if (s.charAt(i) != s.charAt(j)){
                dp[i][j] = false;
            }else {
                if (j - i < 3){
                    dp[i][j] = true;
                }else {
                    dp[i][j] = dp[i + 1][j - 1];
                }
            }
            // 記錄最長迴文資訊
            if (dp[i][j] && j-i+1 > length){
                start = i;
                length = j - i + 1;
            }
        }
    }
    return s.substring(start,length);
}

以上程式碼分析：1 雙重for循環，計算出dpTable中的值；2 最長迴文資訊只需記錄起點和長度即可，當然也可記錄起止位置，效果一樣; 3 s.charAt(i) != s.charAt(j) 且 subStr(i,j)長度大於3 時，才會使用狀態轉移方程！

至此，尋找迴文字元串演算法你學會了嗎？

「全文完！」

我近期其他文章：

只寫原創，敬請關注