概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。
その対策としてLeetCodeなるサイトで対策を行うようだ。
早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイト。
せっかくだし人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。
前回
ゼロから始めるLeetCode Day50「739. Daily Temperatures」
今はTop 100 Liked QuestionsのMediumを優先的に解いています。
Easyは全て解いたので気になる方は目次の方へどうぞ。
Twitterやってます。
問題
647. Palindromic Substrings
難易度はMedium。
Top 100 Liked Questionsからの抜粋です。
問題としては、文字列sが与えられます。
この文字列内の回文の数を数え、その数を返すアルゴリズムを実装してください、というものです。
なお、開始インデックスまたは終了インデックスが異なる部分文字列は、同じ文字で構成されていても、異なる部分文字列としてカウントされます。
Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
解法
よくある回文のチェック方法としては最初から文字列を舐めたものと反対から舐めていったものが一致すれば回文であるということになります。
Bruteforce(総当たり)でよければfor文を二重に回せば良いことになりますが、for文を2重に回すと計算量がO(N^2)になってしまい、とても遅くなってしまいます。
class Solution:
def countSubstrings(self, s: str) -> int:
ans = 0
if not s:
return ans
for i in range(len(s)):
ans += 1
for j in range(1, i+1):
if self.is_palindrom(s[i-j:i+1]):
ans += 1
return ans
def is_palindrom(self, s):
return s == s[::-1]
# Runtime: 604 ms, faster than 13.54% of Python3 online submissions for Palindromic Substrings.
# Memory Usage: 13.8 MB, less than 81.86% of Python3 online submissions for Palindromic Substrings.
他にどんな解き方があるかdiscussを見てみましょう。
例えば、この解答法です。
class Solution:
def countSubstrings(self, s: str) -> int:
L, r = len(s), 0
for i in range(L):
for a,b in [(i,i),(i,i+1)]:
while a >= 0 and b < L and s[a] == s[b]: a -= 1; b += 1
r += (b-a)//2
return r
# Runtime: 132 ms, faster than 71.16% of Python3 online submissions for Palindromic Substrings.
# Memory Usage: 13.8 MB, less than 71.36% of Python3 online submissions for Palindromic Substrings.
while文の条件付けの部分が肝ですね。
こういった風に漏れなくダブりなくしっかりとフローを考えられるのはとてもすごいと思いました。
パッと見でもある程度分かりやすいですし、英語ではありますが、詳しく解説してくださっているので気になる方はリンク先で確認してみると良いかもしれません。
今日はここまで。お疲れ様でした。