ゼロから始めるLeetCode Day51 「647. Palindromic Substrings」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。
Twitterやってます。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day50「739. Daily Temperatures」
次回
ゼロから始めるLeetCode Day52 「1351. Count Negative Numbers in a Sorted Matrix」

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文の条件付けの部分が肝ですね。
こういった風に漏れなくダブりなくしっかりとフローを考えられるのはとてもすごいと思いました。

パッと見でもある程度分かりやすいですし、英語ではありますが、詳しく解説してくださっているので気になる方はリンク先で確認してみると良いかもしれません。

今日はここまで。お疲れ様でした。