#概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。
その対策としてLeetCodeなるサイトで対策を行うようだ。
早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイト。
せっかくだし人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。
前回
ゼロから始めるLeetCode Day42「2. Add Two Numbers」
今はTop 100 Liked QuestionsのMediumを解いています。
Easyは全て解いたので気になる方は目次の方へどうぞ。
Twitterやってます。
問題
5. Longest Palindromic Substring
難易度はMedium。
Top 100 Liked Questionsからの抜粋です。
文字列であるsが与えられるのでその文字列の中で最も長い回文（どちらから読んでも同じになる）を探し出すようなアルゴリズムを設計してください。
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Input: "cbbd"
Output: "bb"
以前解いた、
ゼロから始めるLeetCode Day30「234. Palindrome Linked List」
こちらに似ていますが、前回はあくまで与えられた連結リストが回文であるかをチェックするだけであったのに対し、今回は文字列でその中から最長のものを抽出するというものに変わっており、少し複雑になっています。
解法
とはいえ、回文の問題のオーソドックスな考え方は前回のような要素をひっくり返した物を舐めていくものと元々の要素を比較し、仮に一致するのであれば比較を続け、そうでなければそれらの文字列を用意した文字列に保存しておく、というものでしょう。
例えば、例として与えられている"babad"であれば、
babad
と
dabab
を前から一緒に舐めていき、一致する一つ目のaから二つ目のaまでを元々保存してある文字列の長さと比べ、要素が長い方を残すようにし、最後にその文字列を返せば解けそうです。
問題はその要素の舐め方をどのように設定するかですが、反転はスライスの[::-1]で簡単に実装できます。
なので、O(N^2)にはなりますが、for文を二つ回すという荒技で解いてみましょう。
class Solution:
def longestPalindrome(self, s: str) -> str:
if not s:
return ""
for i in range(len(s),0,-1):
for j in range(len(s)-i+1):
if s[j:i+j] == s[j:i+j][::-1]:
return s[j:i+j]
# Runtime: 4884 ms, faster than 25.37% of Python3 online submissions for Longest Palindromic Substring.
# Memory Usage: 13.7 MB, less than 22.69% of Python3 online submissions for Longest Palindromic Substring.
流石に遅いですね・・・
めちゃくちゃ速い回答例としては、以下のようなものがありました。
class Solution(object):
def longestPalindrome(self, s: str) -> str:
if len(s) < 2:
return s
start = 0
maxLen = 1
i = 0
while i < len(s):
l = i
r = i
while r < len(s) - 1 and s[r] == s[r+1]:
r += 1
i = r + 1
while r < len(s)-1 and l > 0 and s[r+1] == s[l-1]:
l -= 1
r += 1
if maxLen < r - l + 1:
start = l
maxLen = r - l + 1
return s[start: start + maxLen]
# Runtime: 116 ms, faster than 95.05% of Python3 online submissions for Longest Palindromic Substring.
# Memory Usage: 13.8 MB, less than 22.69% of Python3 online submissions for Longest Palindromic Substring.
スッゲェ速い！！！！！
勉強すべきことは尽きませんね。とても良いです。
では今回はここまで。お疲れ様でした。