[LeetCode] 0005. 最長回文部分文字列

Python、C++、JavaScript、SQL、TypeScript の多様な LeetCode ソリューションを探索してください。面接の準備、学習、複数のプログラミング言語でのコードの練習に最適です。 Github リポジトリリンク

文字列を与える s、戻る最長 回文の 部分文字列 で s.

例 1:

入力： s = "ババド"
出力： 「バブ」
説明： 「aba」も有効な答えです。

例 2:

入力： s = "cbbd"
出力： 「bb」

制約:

1 <= s.length <= 1000
s 数字と英語の文字のみで構成されます。

パイソン

				
					# 時間計算量: O(n) # 空間計算量: O(n) # Manacher のアルゴリズム クラス ソリューション: def longestPalindrome(self, s: str) -> str: sPrime = "#" + "#".join(s) + "#" n = len(sPrime) palindromeRadii = [0] * n center = radius = 0 for i in range(n): mirror = 2 * center - i if i < radius: palindromeRadii[i] = min(radius - i, palindromeRadii[mirror]) while ( i + 1 + palindromeRadii[i] < n and i - 1 - palindromeRadii[i] >= 0 and sPrime[i + 1 + palindromeRadii[i]] == sPrime[i - 1 - palindromeRadii[i]] ): palindromeRadii[i] += 1 if i + palindromeRadii[i] > radius: center = i radius = i + palindromeRadii[i] maxLength = max(palindromeRadii) centerIndex = palindromeRadii.index(maxLength) startIndex = (centerIndex - maxLength) // 2 longestPalindrome = s[startIndex: startIndex + maxLength] return longestPalindrome # Brute Force # 時間計算量: O(n^3) # 空間計算量: O(n^3) クラス ソリューション: def longestPalindrome(self, s: str) -> str: def check(i, j): left = i right = j - 1 while left < right: if s[left] != s[right]: return False left += 1 right -= 1 return True for length in range(len(s), 0, -1): for start in range(len(s) - length + 1): if check(start, start + length): return s[start: start + length] return "" # 時間計算量: O(n^2) # 空間計算量: O(n^2) # 動的プログラミングクラスのソリューション: def longestPalindrome(self, s: str) -> str: n = len(s) dp = [[False] * n for _ in range(n)] ans = [0, 0] for i in range(n): dp[i][i] = True for i in range(n-1): if s[i] == s[i+1]: dp[i][i+1] = True ans = [i, i+1] for diff in range(2, n): for i in range(n - diff): j = i + diff s[i] == s[j] かつ dp[i+1][j-1] の場合: dp[i][j] = True ans = [i, j] i, j = ans return s[i:j+1] s = "babad" print(Solution().longestPalindrome(s)) s = "cbbd" print(Solution().longestPalindrome(s))

パイソン

関連記事