LeetCode之最長回文串（409）、最長回文子串（5）、回文子串（647）、計數二進制子串（696）

1、最長回文串（409）

題目描述：

【簡單】

給定一個包含大寫字母和小寫字母的字元串，找到通過這些字母構造成的最長的回文串。

在構造過程中，請注意區分大小寫。比如 “Aa” 不能當做一個回文字元串。

注意:

假設字元串的長度不會超過 1010。

示例 1:

輸入:
"abccccdd"

輸出:
7

解釋:
我們可以構造的最長的回文串是"dccaccd", 它的長度是 7。
           

題目連結

• 有點熟悉呀，哦！之前做過回文數這道題

思路分析：

要求：基于字元串所有字元，構造最長回文串

回文串：正着讀和反着讀都一樣的字元串

\quad \quad 在一個回文串中，隻有最多一個字元出現了奇數次，其餘的字元都出現偶數次。那麼。對于次數為偶數次的字元，那麼所有此字元都可以構成回文串的一部分；對于次數為奇數次的字元，那麼所有此字元-1都可以構成回文串的一部分;最後，我們任意加一個奇數次字元即可構成最長回文串。是以，思路如下：

• 對字元計數，偶數直接加上，奇數-1加上
• 最後若出現過奇數次的字元，在加個1（回文中間的字元）

class Solution:
    def longestPalindrome(self, s: str) -> int:
        odd=0 #标記是否出現過奇數次數的字元,0記沒有出現過
        res=0 
        counts={}#統計字元次數
        for i in s:
            counts[i]=counts.get(i,0)+1
        for key in counts.keys():
            if counts[key]%2==0:
                res+=counts[key]
            else:
                res+=counts[key]-1
                odd=max(odd,counts[key])
        return res if odd==0 else res+1
           

• 時間複雜度： O ( N ) O(N) O(N)
• 空間複雜度： O ( S ) O(S) O(S)，其中 S為字元集不同字元數。

2、最長回文子串（5）

題目描述：

【中等】

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

示例 1:

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

題目連結

題解一：暴力法

• 列舉所有的子串，判斷是否為回文串，儲存最長的回文串。

class Solution:
    #判斷字元串是否為回文字元串
    def validate_palindrome(self,s:str,left:int,right:int) -> bool:
        if len(s)<right and left<0:
            assert("s length must greater than right,left must greater than or equal to zero")
        while left < right:
            if s[left]!=s[right]:
                return False
            left+=1
            right-=1
        return True

    def longestPalindrome(self, s: str) -> str:
        n=len(s)
        if n<2:
            return s
        #用來記錄回文字元串
        palindrome_s=s[0]
        #記錄回文字元串長度
        max_len=1
        for i in range(n-1):
            for j in range(i+1,n):
                if j-i+1>max_len and self.validate_palindrome(s,i,j):
                    palindrome_s=s[i:j+1]
                    max_len=j-i+1
        return palindrome_s
           

• 時間複雜度： O ( n ³ ） O(n³） O(n³）兩層 for 循環 O(n²），for 循環裡邊判斷是否為回文 O(n），是以時間複雜度為 O(n³）。
• 空間複雜度：O(1）常數個變量。
• 可以通過，但是超過時間限制，舍棄

題解二：動态規劃

• 狀态：

  dp[i][j] 表示子串 s[i…j] 是否為回文子串，這裡子串 s[i…j] 定義為左閉右閉區間，可以取到 s[i] 和 s[j]。

• 狀态轉移方程：

  dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]

• 初始化：

  初始化的時候，單個字元一定是回文串，

  是以當字元串的長度小于2時，肯定為回文串，且把對角線先初始化為 true，即 dp[i][i] = true 。

• 輸出：

  隻要一得到 dp[i][j] = true，就記錄子串的長度和起始位置，沒有必要截取，這是因為截取字元串也要消耗性能，記錄此時的回文子串的「起始位置」和「回文長度」即可。

注意事項：總是先得到小子串的回文判定，然後大子串才能參考小子串的判斷結果，即填表順序很重要。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n=len(s)
        #考慮特殊情況：如果字元串的長度為1就是回文字元串
        if n<2:
            return s
        #建立一個二維清單用來儲存每個字元串是否為回文字元串
        is_p= [[False] * n for _ in range(n)]
        #對角線上都是回文字元串，因為都是單個字元
        for i in range(n):
            is_p[i][i]=True
        #用來記錄回文字元串的起始位置
        s_index=0
        max_len=1
        #周遊表格，計算字元串是否為回文字元串
        for j in range(1,n):
            for i in range(0,j):
                if s[i]==s[j]:
                    if j-i<3:
                        is_p[i][j]=True
                    else:
                        is_p[i][j]=is_p[i+1][j-1]
                else:
                    is_p[i][j]=False
                #記錄最長的回文字元串
                current_len=j-i+1
                if is_p[i][j] and current_len>max_len:
                    max_len=current_len
                    s_index=i
        return s[s_index:(s_index+max_len)]
           

• 時間複雜度： O ( n 2 ) O(n^2) O(n2)
• 空間複雜度： O ( n 2 ) O(n^2) O(n2)

題解三：中心擴散算法

• 周遊每一個索引，以這個索引為中心，利用“回文串”中心對稱的特點，往兩邊擴散，看最多能擴散多遠。
• 回文串在長度為奇數和偶數的時候，“回文中心”的形式是不一樣的。
  • 奇數回文串的“中心”是一個具體的字元，例如：回文串 “aba” 的中心是字元 “b”；
  • 偶數回文串的“中心”是位于中間的兩個字元的“空隙”，例如：回文串串 “abba” 的中心是兩個 “b” 中間的那個“空隙”。

class Solution:
    def center_spread(self,s,size,left,right):
        """中心擴散尋找回文字元串
        :param s: 字元串
        :param size: 字元串的長度
        :param left: 開始尋找左邊的位置
        :param right: 開始尋找右邊的位置
        :return: 回文字元串,回文字元串的長度
        """
        i=left
        j=right
        #保證在尋找的過程中不發生越界,而且左右兩個字元要相等
        while i>=0 and j<size and s[i]==s[j]:
            i-=1
            j+=1
        return s[i+1:j],j-i+1
    def longestPalindrome(self, s: str) -> str:
        size=len(s)
        if size<2:
            return s
        s_palindrome=s[0]
        max_len=1
        for i in range(size):
            #當回文字元串數是奇數時
            odd_palindrome,odd_len=self.center_spread(s,size,i,i)
            #當回文字元串是偶數的時候
            even_palindrom,even_len = self.center_spread(s,size,i,i+1)
            #擷取最長的回文字元串
            cur_palindrome = odd_palindrome if odd_len > even_len else even_palindrom
            #更新最長的回文字元串
            if len(cur_palindrome) > max_len:
                s_palindrome = cur_palindrome
                max_len = len(cur_palindrome)

        return s_palindrome

           

• 時間複雜度： O ( n 2 ) O(n^2) O(n2)
• 空間複雜度： O ( 1 ) O(1) O(1)

3、回文子串（647）

題目描述：

【中等】

給定一個字元串，你的任務是計算這個字元串中有多少個回文子串。

具有不同開始位置或結束位置的子串，即使是由相同的字元組成，也會被視作不同的子串。

示例 1：

輸入："abc"
輸出：3
解釋：三個回文子串: "a", "b", "c"
           

示例 2：

輸入："aaa"
輸出：6
解釋：6個回文子串: "a", "a", "a", "aa", "aa", "aaa"
           

題目連結

思路分析：

4、計數二進制子串（696）

題目描述：

【簡單】

給定一個字元串 s，計算具有相同數量0和1的非空(連續)子字元串的數量，并且這些子字元串中的所有0和所有1都是組合在一起的。

重複出現的子串要計算它們出現的次數。

示例1：

輸入: "00110011"
輸出: 6
解釋: 有6個子串具有相同數量的連續1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。

請注意，一些重複出現的子串要計算它們出現的次數。

另外，“00110011”不是有效的子串，因為所有的0（和1）沒有組合在一起。

           

示例2：

輸入: "10101"
輸出: 4
解釋: 有4個子串：“10”，“01”，“10”，“01”，它們具有相同數量的連續1和0。
           

注意：

• s.length 在1到50,000之間。
• s 隻包含“0”或“1”字元。

題目連結

思路分析：