【小Y學演算法】??每日LeetCode打卡??——5.最長回文子串

📢前言

• 🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻
• 🌲 每天打卡一道演算法題，既是一個學習程序，又是一個分享的程序😜
• 🌲 提示：本專欄解題 編程語言一律使用 C# 和 Java 兩種進行解題
• 🌲 要保持一個每天都在學習的狀態，讓我們一起努力成為演算法大神吧🧐！
• 🌲 今天是力扣演算法題持續打卡第5天🎈！
• 🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻

🌲原題樣例

給你一個字串 s，找到 s 中最長的回文子串，

示例 1：

輸入：s = “babad”
輸出：“bab”
解釋：“aba” 同樣是符合題意的答案，

示例 2：

輸入：s = “cbbd”
輸出：“bb”

示例 3：

輸入：s = “a”
輸出：“a”

示例 4：

輸入：s = “ac”
輸出：“a”

提示：

• 1 <= s.length <= 1000
• s 僅由數字和英文字母（大寫和/或小寫）組成

回文串含義

這里簡單解釋一下什么是回文串~

"回文串”就是一個正讀和反讀都一樣的字串，比如“mom”或者“noon”等等就是回文串，

顧名思義，“回文子串”的意思是一個字串中的回文串，比如字串“baba”中就包含有“bab”和“aba”這兩個回文子串

🌻C#方法一：暴力法

解題思路

首先我們會想到使用 暴力法 來解決題目，用3層回圈來對每個子串進行檢查，最后取最長的子串作為結果，這樣時間復雜度為 O(n^3) ，
然后可能會考慮到使用動態規劃的方式，以空間來換取時間,可以將時間復雜度優化為 O(n^2)，但相應的空間復雜度會增大

public class Solution {
    public string LongestPalindrome(string s)
    {
        string result = "";
        int n = s.Length;
        for (int i = 0; i < n; i++)
        {
            for (int j = i; j < n; j++)
            {
                // 檢查 s[i]到s[j]是否是回文串，如果是，且長度大于result長度，就更新它
                int p = i, q = j;
                bool isPalindromic = true;
                while (p < q)
                {
                    if (s[p++] != s[q--])
                    {
                        isPalindromic = false;
                        break;
                    }
                }
                if (isPalindromic)
                {
                    int len = j - i + 1;
                    if (len > result.Length)
                    {
                        result = s.Substring(i, len);
                    }
                }

            }
        }
        return result;
    }

}
鏈接：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/leetcode-5-longest-palindromic-substring-zui-chang/

執行結果
執行結果 通過，執行用時 1708ms，記憶體消耗 26.5 MB

復雜度分析

時間復雜度： O(n^3)
空間復雜度：O(1)

🌻C#方法二：中心擴展法

對于回文串，我們可以找到一個中心，從這個中心向兩邊擴展的話，兩邊對應的值是相等的，按照這個邏輯，我們只需要一層主回圈 i 將 s 遍歷一遍即可,并在回圈內部 將s[i]視為中心 使用中心擴展法來求出以s[i]為中心的最長的回文串；當i將s遍歷完后，即可得到s的最長回文串，

下面我們以 s=“abcbc”, 且 i==2 為例，討論一下如何進行中心擴展，

1. i==2指向c，我們初始化兩個指標p與q都指向這個c
2. p–，q++，p指向了左邊b，q指向了右邊b
3. 因為s[p]==s[q], 所以再次執行p–,q++,此時p指向了最左邊a，q指向了最右邊c
4. 因為s[p]!=s[q],所以結束擴展，

此時，我們得到了當i指向中間c時的最長回文子串為"bcb",長度為 q-p-1,開始位置為p+1. 對應圖解圖下：

當子串長度為奇數時，這個邏輯很容易理解； 當子串長度為偶數時，比如 “abba”，我們需要把中心理解為中軸線，即中軸線在兩個b的中間，

將中心理解為中軸線后，中軸線既可以在整數位上，例如"aba"中的b，也可以在兩數之間，例如"abba"中的bb之間，若我們用mid表示中軸線，則mid可以等于0、1、2… 也可以等于0.5、1.5、2.5… 對于長度為n的陣列，中軸線的選擇有 n 個，i 的取值為0到 2(n-1) .，

代碼為：

public class Solution {
    public string LongestPalindrome(string s)
    {
        string result = "";
        int n = s.Length;
        int end = 2 * n - 1;
        for (int i = 0; i < end; i ++)
        {
            double mid = i / 2.0;
            int p = (int)(Math.Floor(mid));
            int q = (int)(Math.Ceiling(mid));
            while (p >= 0 && q < n)
            {
                if (s[p] != s[q]) break;
                p--; q++;
            }
            int len = q - p - 1;
            if (len > result.Length)
                result = s.Substring(p + 1, len);
        }
        return result;
    }
}
鏈接：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/leetcode-5-longest-palindromic-substring-zui-chang/

執行結果
執行結果 通過，執行用時88ms，記憶體消耗 26 MB

復雜度分析

時間復雜度： O(n^2)
空間復雜度：O(1)

🌻Java方法一：動態規劃

Java方法也是力扣官方對此題的解答，可以參考答案

根據這個思路，我們就可以完成動態規劃了，最終的答案即為所有 P(i, j) = \text{true}P(i,j)=true 中 j-i+1j?i+1（即子串長度）的最大值，注意：在狀態轉移方程中，我們是從長度較短的字串向長度較長的字串進行轉移的，因此一定要注意動態規劃的回圈順序，

public class Solution {

    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }

        int maxLen = 1;
        int begin = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        boolean[][] dp = new boolean[len][len];
        // 初始化：所有長度為 1 的子串都是回文串
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }

        char[] charArray = s.toCharArray();
        // 遞推開始
        // 先列舉子串長度
        for (int L = 2; L <= len; L++) {
            // 列舉左邊界，左邊界的上限設定可以寬松一些
            for (int i = 0; i < len; i++) {
                // 由 L 和 i 可以確定右邊界，即 j - i + 1 = L 得
                int j = L + i - 1;
                // 如果右邊界越界，就可以退出當前回圈
                if (j >= len) {
                    break;
                }

                if (charArray[i] != charArray[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此時記錄回文長度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }
}

執行結果
執行結果 通過，執行用時178ms，記憶體消耗 42.9 MB

復雜度分析

時間復雜度： O(n^2)
空間復雜度：O(n^2)

🌻Java方法一：中心擴展演算法

思路與演算法

可以發現，所有的狀態在轉移的時候的可能性都是唯一的，也就是說，我們可以從每一種邊界情況開始「擴展」，也可以得出所有的狀態對應的答案，

邊界情況即為子串長度為 11 或 22 的情況，我們列舉每一種邊界情況，并從對應的子串開始不斷地向兩邊擴展，如果兩邊的字母相同，我們就可以繼續擴展，例如從 P(i+1,j-1)P(i+1,j?1) 擴展到 P(i,j)P(i,j)；如果兩邊的字母不同，我們就可以停止擴展，因為在這之后的子串都不能是回文串了，

聰明的讀者此時應該可以發現，「邊界情況」對應的子串實際上就是我們「擴展」出的回文串的「回文中心」，方法二的本質即為：我們列舉所有的「回文中心」并嘗試「擴展」，直到無法擴展為止，此時的回文串長度即為此「回文中心」下的最長回文串長度，我們對所有的長度求出最大值，即可得到最終的答案，

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(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 expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            --left;
            ++right;
        }
        return right - left - 1;
    }
}

執行結果
執行結果 通過，執行用時38ms，記憶體消耗 30.8 MB

復雜度分析

時間復雜度： O(n^2)
空間復雜度：O(1)

💬總結

• 今天是力扣演算法題打卡的第五天！今天的題有點難，借助力扣大神題解看了半天！
• 文章采用 C# 和 Java 兩種編程語言進行解題
• 一些方法也是參考力扣大神寫的，也是邊學習邊分享，再次感謝演算法大佬們
• 那今天的演算法題分享到此結束啦，明天再見！