leetcode_187.py

from typing import List
class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        import collections
        table = {"A":0, "C":1, "G":2, "T": 3} # 2bit表現
        if s is None:
            return []
        ll = len(s)
        if ll < 10:
            return []
        hashVal = 0 # 今までのハッシュ値
        hashHistroy = collections.defaultdict(int) # unordered_map<int,int>
        hashStr = dict() # 結果表示用のunordered_map<int,str>
        # 最初の10文字を計算する
        for i in range(10):
            hashVal <<= 2
            hashVal |= table[s[i]]
            hashVal &= ( (1<<20) - 1) # bitmask 011111111...
        # 最初の10文字の処理
        hashHistroy[hashVal] += 1
        hashStr[hashVal] = s[0:10]
        for i in range(1, ll - 9): # 1文字目から最後までループ
            hashVal <<= 2 # 抜ける数字をシフトして
            hashVal &= ( (1<<20) - 1) # 20bitだけ残す = 抜ける数字を消す
            hashVal |= table[s[i+9]] # 新しく入る数字をORで入れる
            hashHistroy[hashVal] += 1 # このハッシュの回数をカウント
            hashStr[hashVal] = s[i:i + 10]  # 今の10文字が答えになったときのために保存
        # 復元。ハッシュのカウントを数えて、2回以上なら、結果として表示
        res = []
        for k in hashHistroy.keys():
            if hashHistroy[k] > 1:
                res.append(hashStr[k])
        return res