第6章6文字列操作(最長のパリンドロン部分文字列)

1609 ワード
パイ アルゴリズム#アルゴリズム# テキストリンク
最長のファリンドロン部分文字列を出力します.
例1:
Input: s = "babad"
Output: "bab"
備考:「aba」も正解です.
class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand(left, right):
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return s[left+1:right]
        
        if len(s) < 2 or s == s[::-1]:
            return s
        
        result = ''
        
        #양 옆으로 펼쳐나가기를 시작할 지정
        for i in range(len(s) - 1): # 0 ~ n-1
            result = max(result,expand(i, i),expand(i, i+1),key=len)
        return result
def expand(left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
expandという名前の関数を作成します.
条件は、左が0より大きく、右が文字列より小さいことです.そしてs[left]とs[right]は等しい.
left -= 1
right += 1
return s[left+1:right]
左は1、右は1、真ん中は1、最後は戻ります.
if len(s) < 2 or s == s[::-1]:
           return s
文字列が2より小さい場合は、1つの単語だけが最大のパリンドロンであるか、文字列全体が逆方向である場合と同じである場合は、比較する必要はありません.
そうでなければ、他の方法で最大のパリン症候群を見つける必要があります.まずresult='で初期化します.
for i in range(len(s) - 1): # 0 ~ n-1
           result = max(result,expand(i, i),expand(i, i+1),key=len)
       return result
テキストを展開し、最も長いものを印刷し、最大値を取ります.resultが有する長さ、expand(i,i)偶数パリンドロン、expand(i,i+1)奇数パリンドロンは、3つの場合で最長値を有する長さがキー値となる.
そしてその値を返します.
Servlet
Webフロントエンド開発--ラブキューブ