5.Leetcode-Longest Paildrome Substring[二重ポインタ]

10169 ワード
two pointer algorithm テキストリンク
質問リンク

私の答え


フィリンドロンを使用するか否かを判定するisPalindrome関数を生成し,部分文字列の長さから順にフィリンドロンを使用するか否かを判定する.フィリンドロムの場合は、すべての関数を返して終了します.
### leetcode 5
## Longest_Paildrome_Substring
# 가장 긴 팰린드롬 부분 문자열을 출력하라. 

class Solution:
   
    def longestPalindrome(self, s: str) -> str:
        
        def ispalidrome(str1):
            if str1 == str1[::-1]:
                return True
        
            return False
        
        for i in range(len(s),0,-1):
            for j in range(len(s) - i+1):
                if ispalidrome(s[j:j+i]):
                    return s[j:j+i]
runtime

Memory

二重ポインタで解く


主にペリン・ドロンを評価するために、2種類に分けることができます.
1)長さが「bb」と同じ偶数のフィリンドロン
2)長さが「bab」のように奇数のフィリングドロン
すなわち、babadという文字列にナビゲートすると.
奇数のフィリングドロンの長さをチェックし、偶数のフィリングドロンの長さをチェックして、最も長い文字列を探します.
従って,expand関数によりこの現象が存在するか否かを判断できる.
  • フェリンドロンなら、折り返し運賃はありますが、
  • フィリンドロンでない場合、戻り値s[left+1:right-1]、すなわちleft+1=right-1は同じであるため、戻り値は別途導出されない.
    • #펠린드롬 여부 판단
def expand(left, right):
    while left >= 0  and right <= len(s) and s[left] == s[right-1]:
        left -= 1
        right += 1

    return s[left + 1: right - 1]

    完全な回答

    class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand(left, right):
            while left >= 0  and right <= len(s) and s[left] == s[right-1]:
                left -= 1
                right += 1

            return s[left + 1: right - 1]

        # 길이가 2보다 작을 경우 그 단어는 펠린드롬이다.
        if len(s) < 2 or s == s[::-1]:
            return s
        
        result = ""
        
        for i in range(len(s)-1):
            result = max(result, expand(i,i+1), expand(i,i+2), key=len)
        
        return result
  • expand(i,i+1)検査長さが「bab」に等しいフィリンドロン
  • expand(i,i+2)により「bb」と同じ偶数長のフィリンドロンを調べた.

    結果


    ランタイム結果

    記憶結果

    従来の実行結果に比べて、メモリと実行時間が大幅に減少しました.
    • go-libp 2 p-kad-dht bootstrapソースコード分析
    スライドJavaScriptコード