ゼロから始めるLeetCode Day66「438. Find All Anagrams in a String」

概要

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

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

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

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

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

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day65「560. Subarray Sum Equals K」

次回
[ゼロから始めるLeetCode Day67 「1486. XOR Operation in an Array」]((https://kueharx.blogspot.com/2020/06/leetcode-day67-1486-xor-operation-in.html)

Twitterやってます。

問題

438. Find All Anagrams in a String

難易度はMedium。
Top 100 Liked Questionsからの抜粋です。

文字列sと空でない文字列pが与えられたとき、sの中のpのアナグラムの開始インデックスをすべて求めなさい、という問題です。

Stringsは英小文字のみで構成され、sとpの長さはともに20,100を超えてはいけません。

なお、出力の順番は関係ありません。

Example 1:

Input:
s: “cbaebabacd” p: “abc”

Output:
[0, 6]

Explanation:
The substring with start index = 0 is “cba”, which is an anagram of “abc”.
The substring with start index = 6 is “bac”, which is an anagram of “abc”.

Example 2:

Input:
s: “abab” p: “ab”

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is “ab”, which is an anagram of “ab”.
The substring with start index = 1 is “ba”, which is an anagram of “ab”.
The substring with start index = 2 is “ab”, which is an anagram of “ab”.

解法

アナグラムの開始のインデックスを整理する必要があります。
解法としてはSliding Windowというアルゴリズムが有名なようで、別に記事を書く予定です。
ネットワークでは聞いたことのあるワードですがアルゴリズムで聞いたことはなかったですね。

ただ、ロジックを真似て書いてみたものが以下のように

import collections
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        len_s,len_p,set_p,ans = len(s),len(p),Counter(p),[]
        for i in range(len_s-len_p+1):
            if Counter(s[i:i+len_p]) == set_p:
                ans.append(i)
        return ans
# Runtime: 7868 ms, faster than 7.31% of Python3 online submissions for Find All Anagrams in a String.
# Memory Usage: 14.8 MB, less than 69.94% of Python3 online submissions for Find All Anagrams in a String.

めちゃくちゃ遅くて、これはどうしたもんかと思いました・・・

とりあえずdiscussを見て理解してみようと試みました。

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
    	LS, LP, S, P, A = len(s), len(p), 0, 0, []
    	if LP > LS: return []
    	for i in range(LP): S, P = S + hash(s[i]), P + hash(p[i])
    	if S == P: A.append(0)
    	for i in range(LP, LS):
    		S += hash(s[i]) - hash(s[i-LP])
    		if S == P: A.append(i-LP+1)
    	return A

するとこんな解答が。
コードを見てみると、counterを使う代わりにハッシュマップを使っていて、残りは大きく変わることはなさそうです。

とりあえずスピードを見てみると・・・

Runtime: 68 ms, faster than 99.89% of Python3 online submissions for Find All Anagrams in a String.
Memory Usage: 14.9 MB, less than 42.94% of Python3 online submissions for Find All Anagrams in a String.

！？

とんでもなく、速いですね・・・
確かに考えてみればCounterを要素の度に回すと明らかに効率悪いですよね・・・
for文で回す時にその度に要素を全て回してdicで返すということは、要素が多ければ多いほど飛躍的に遅くなっていくというかなり悪い実装方法です。

しかしHashMapに入れるという発想はなかったですね・・
discussを見てるとこういう発想に出会えるのでしっかりみることが重要ですね。

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