【LeetCode 中等題】84-重複的DNA序列

題目描述：所有 DNA 由一系列縮寫為 A，C，G 和 T 的核苷酸組成，例如：“ACGAATTCCG”。在研究 DNA 時，識别 DNA 中的重複序列有時會對研究非常有幫助。

編寫一個函數來查找 DNA 分子中所有出現超多一次的10個字母長的序列（子串）。

示例:

輸入: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

輸出: ["AAAAACCCCC", "CCCCCAAAAA"]      

解法1。利用python裡對字元串切片和字典的便利性，使用一個字典存儲出現過的長度為10的子串，一次隻取長度為10的子串

class Solution:
    def findRepeatedDnaSequences(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        if len(s)<10:
            return []
        else:
            res = []
            appeared = {}
            for i in range(len(s)-9): # 注意次數的上限，經過驗算是len(s)-9而非len(s)-10
                tmp = s[i:i+10]
                if tmp not in appeared:
                    appeared[tmp] = 1
                elif appeared[tmp] == 1: # 在tmp出現2次時放到res裡，之後就不放，避免重複
                    res.append(tmp)
                    appeared[tmp] += 1
            return res
           

解法2。位運算的方法，其實就是将鍵值由字元串轉譯成了二進制int數，節省空間和時間。

• 此題由于構成輸入字元串的字元隻有四種，分别是A, C, G, T，下面我們來看下它們的ASCII碼用二進制來表示：
  • A: 0100 0001
  • C: 0100 0011
  • G: 0100 0111
  • T: 0101 0100
• 是以對每個字元得到其ord('')後&7獲得後3位，這樣得到一個30位長的鍵值，存在字典，若出現2次就放到res裡
• 初始化就先獲得前9個字元的後三位，例如取出前9個字元AAAAACCCC，根據上面的分析，我們用三位來表示一個字元，是以這9個字元可以用二進制表示為001001001001001011011011011，然後從第10個字元開始周遊，取後27位（後9個字元）再或新的字元後3位，實作将目前字元加進來和第一個最先出現的字元去掉

class Solution:
    def findRepeatedDnaSequences(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        if len(s)<10:
            return []
        else:
            res = []
            appeared = {}
            mask = 0x7ffffff
            cur = 0
            for i in range(9):
                cur = (cur<<3) | (ord(s[i])&7)
            for i in range(9,len(s)):
                cur = (cur&mask)<<3 | (ord(s[i])&7)
                if cur not in appeared:
                    appeared[cur] = 1
                else:
                    if appeared[cur] == 1:
                        res.append(s[i-9:i+1])
                    appeared[cur] += 1
            return res
           

參考連結：https://www.cnblogs.com/grandyang/p/4284205.html