题目描述：

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example,

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

Return:
["AAAAACCCCC", "CCCCCAAAAA"].

题目大意：

DNA由一系列简写为A,C,G,T的碱基组成，例如"ACGAATTCCG"。研究DNA时，识别DNA中的重复序列有时候会有用处。

写一个函数找出DNA分子中所有不止一次出现的10字母长度的子串序列。

解题思路：

字典+位运算，或者进制转换。

由于直接将字符串存入字典会导致Memory Limit Exceeded，采用位操作将字符串转化为整数可以减少内存开销。

Python代码：

class Solution:
    # @param s, a string
    # @return a list of strings
    def findRepeatedDnaSequences(self, s):
        ans = []
        valCnt = dict()
        map = {'A' : 0, 'C' : 1, 'G': 2, 'T' : 3}
        sum = 0
        for x in range(len(s)):
            sum = (sum * 4 + map[s[x]]) & 0xFFFFF
            if x < 9:
                continue
            valCnt[sum] = valCnt.get(sum, 0) + 1
            if valCnt[sum] == 2:
                ans.append(s[x - 9 : x + 1])
        return ans

另外，LeetCode Discuss中还给出了更加简短高效的C++代码

链接：https://oj.leetcode.com/discuss/24478/i-did-it-in-10-lines-of-c

vector<string> findRepeatedDnaSequences(string s) {
    unordered_map<int, int> m;
    vector<string> r;
    int t = 0, i = 0, ss = s.size();
    while (i < ss)
        if (m[t = (t << 3 | s[i++] & 7) & 0x3FFFFFFF]++ == 1)
            r.push_back(s.substr(i - 10, 10));
    return r;
}

 

本文链接：http://bookshadow.com/weblog/2015/02/06/leetcode-repeated-dna-sequences/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码