LeetCode5. 最長回文サブストリング(python)

3013 ワード
LeetCode
1つの文字列sが与えられ、sの中で最も長い回文サブ列が見出される.sの最大長さは1000と仮定できます.
例1:
  : "babad"
  : "bab"
  : "aba"         。

例2:
  : "cbbd"
  : "bb"

問題解決の考え方:
manacher
マラ車は文字列を専門に処理するアルゴリズムである.
まず、回文文字列には2種類あります.長さは奇数で、「aba」です.長さは偶数、「abba」です.偶数の長さの返信文字列は文字を対称中心としないが、マラリアアルゴリズムは文字列の各文字間(先頭と末尾の両端を含む)に#（という記号が元の文字列にないように特殊な記号を挿入することによって、パリティの場合を統一する(#a#b#a#,#a#b#a#,長さはいずれも奇数).
次に,回文文字列の性質をうまく利用し,コア式:p[i]=min(max_right-i,p[2*center-i])
この式を解読する前に、いくつかの変数を初期化します.
p ：     0   ，                       
center ：         
max_right ：          
max_s = 0 ：                

ここで、p[0,1,2.....i-1]を求めたとすると、i番目の位置については、
まずiの位置がmax_であると判断するrightの右側か左側か:
ip[j]<=max_の場合right-i,すなわちiにjを加えた点の回文半径の長さはmax_を超えていない.right,iという点の回文半径はp[j]以上であり,暴力的に外へ探索し続け,その点の最長回文サブ列の長さを見つけた.
p[j]>max_の場合right-iではmax_right内の点は必ず対称で、max_からright点は更に外へ暴力的に捜索します;
i>=max_の場合rightは、返信文字列の特徴を利用して、直接暴力的に検索することはできません.
最後に最長文字列と中心点を更新します.
以上、マラチャアルゴリズムは、回文子列の性質を利用して時間の複雑さをO(N^2)からO(N)に下げ、抽象的で分かりにくいので、コードを見るとかなり良いはずです
コード:
class Solution:
    def longestPalindrome(self, s: str) -> str:
        s = "!#" + "#".join(s) + "#?"
        center = 0 #         
        max_right = 0 #          
        max_s = 0 #               

        p = [0] * (len(s)-1)
        for i in range(1, len(s)-1):
            if i < max_right:
                p[i] = min(max_right-i, p[2*center-i])
            else:
                p[i] = 1

            while i-p[i]>0 and i+p[i] max_right:
                max_right = i+p[i]
                center = i
            max_s = max(max_s, p[i])
        
        s=s[p.index(max_s)-(max_s-1): p.index(max_s)+(max_s-1)]
        s=s.replace('#','') 
        
        return s

最后に暴力解法を付け加えて、とても暴力的で暴力的です...
class Solution:
    def countSubstrings(self, s: str) -> int:
        num = []
        for k in range(2, len(s)+1): #k:       
            for i in range(len(s)-(k-1)):
                st = s[i:i+k]
                n = 0
               
                if len(st)%2 == 0:
                    for j in range(int(len(st)/2)):
                        if st[j] == st[len(st)-1-j]:
                            n+=1
                    if n == int(len(st)/2):
                        num.append(st)
                
                else:
                    for j in range(math.floor(len(st)/2)):
                        if st[j] == st[len(st)-1-j]:
                            n+=1
                    if n == math.floor(len(st)/2):
                        num.append(st)
        
        return len(num) + len(s)

Python calendarライブラリの使用
pysparkはpysparkを勉強します.sql module