[2021][01]Longest Palindrome Substring
問題情報
問題の概要
問題では,与えられた文字列sにおいてsの中で最も長いパリンドロン部分の文字列を返す非常に簡単な問題が望ましい.
せいげんじょうけん
質問へのアクセス
Brute Forceで解く方法があります.これは、iの1文字目を中心とした最長部分の文字列をダブルfor文で検索する方法です.この方法で解くと100%タイムアウトになります.
次の方法は動的プログラミングを用いてBrute Forceで繰り返される部分を処理することである.アルゴリズム名はManacherアルゴリズムです.
偶数の長さの文字列の中でManacherアルゴリズムを使用して最も長いパリンドロン部分の文字列が見つからない.したがって、指定された文字列sの間に"#"または"@"を追加する場合、Manacherアルゴリズムを使用して正しい答えを見つけることができます.
コード#コード#
class Solution:
def longestPalindrome(self, s: str) -> str:
def addSharp(string) -> str:
result = '#'
for ss in string:
result += ss + '#'
return result
def manacher(string) -> str:
sharped = addSharp(s)
a = [0] * len(sharped)
p = r = 0
for i in range(len(sharped)):
if i <= r:
a[i] = min(r - i, a[2 * p - i])
else:
a[i] = 0
while i - a[i] -1 >= 0 and i + a[i] + 1 < len(sharped) and sharped[i - a[i] - 1] == sharped[i + a[i] + 1]:
a[i] += 1
if r < i + a[i]:
# r은 반지름이 아니라 i 번째 문자를 중심으로 하는 가장 긴 팔린드롬의 가장 길이
r = i + a[i]
p = i
maxIndex = a.index(max(a))
answer = sharped[maxIndex-a[maxIndex]:maxIndex+a[maxIndex] + 1].replace('#', '')
return answer
return manacher(s)Reference
この問題について([2021][01]Longest Palindrome Substring), 我々は、より多くの情報をここで見つけました https://velog.io/@papayetoo/202101Longest-Palindrome-Substringテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol