LeetCode - 解题笔记 - 187 - Repeated DNA Sequences

Solution 1

由于题目的限制非常直观，因此解法也非常直观。

从初始位置不断向后寻找一个指定长度的子串，并用哈希表进行计数。满足要求时保存结果（注意避免重复判定的问题）。

我想了几个能够简化子串存取的方法（滑窗），但是都不能实际优化复杂度。

• 时间复杂度：$O(NM)$，其$N$为输入的字符串长度，$M$为指定的子串长度，由于每一次判定需要取一个固定长度子串
• 空间复杂度：$O(NM)$，其$N$为输入的字符串长度，$M$为指定的子串长度，子串存取和哈希表占用

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        int seqLen = 10;

        vector<string> ans;
        unordered_map<string, int> seqCounter;
        for (int i = 0; i < s.size(); ++i) {
            if (i >= seqLen - 1) {
                auto tempSeq = s.substr(i - seqLen + 1, seqLen);
                seqCounter[tempSeq]++;
                if (seqCounter[tempSeq] == 2) {
                    // 必须是等于2，不然就会重复计算了
                    ans.push_back(tempSeq);
                }
            }
        }
        
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Solution 2

【官方题解参考】官方题解基于位操作给出了一个滑窗优化方案。

因为题目限制了长度为10，涉及到四种位态，因此可以一个2位表示共20位的子串来保存当前状态，一个int整型数就能解决问题，能够优化扫描时间（滑窗）的同时也能节省存储（整型数的哈希）

• 时间复杂度：$O(N)$，其中$N$为输入的字符串长度，滑窗浏览只需要线性扫描时间
• 空间复杂度：$O(N)$，其中$N$为输入的字符串长度，子串状态存取和哈希表占用

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        int seqLen = 10;
        unordered_map<char, int> char2bin = {{'A', 0}, {'C', 1}, {'G', 2}, {'T', 3}};
        
        vector<string> ans;
        int tempSeq;
        unordered_map<int, int> seqCounter;
        for (int i = 0; i < s.size(); ++i) {
            if (i < seqLen - 1) {
                // 左移 + 右补
                tempSeq = (tempSeq << 2) | char2bin[s[i]];
            } else {
                // 左移 + 右补 + 去头（mask长度为20）
                tempSeq = ((tempSeq << 2) | char2bin[s[i]]) & ((1 << (seqLen * 2)) - 1);
                seqCounter[tempSeq]++;
                if (seqCounter[tempSeq] == 2) {
                    // 必须是等于2，不然就会重复计算了
                    ans.push_back(s.substr(i - seqLen + 1, seqLen));
                }
            }
        }
        
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

Solution 3

Solution 1的Python实现

class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        seqLen = 10
        
        ans = list()
        seqCounter = defaultdict(int)
        for i in range(len(s)):
            if i >= seqLen - 1:
                tempSeq = s[i - seqLen + 1: i + 1]
                seqCounter[tempSeq] += 1
                if seqCounter[tempSeq] == 2:
                    ans.append(tempSeq)
                    
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14

Solution 4

Solution 2的Python实现

class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        seqLen = 10
        char2bin = {'A': 0, 'C': 1, 'G': 2, 'T': 3}
        
        ans = list()
        seqCounter = defaultdict(int)
        tempSeq = 0
        for i in range(len(s)):
            if i < seqLen - 1:
                tempSeq = (tempSeq << 2) | char2bin[s[i]]
            else:
                tempSeq = ((tempSeq << 2) | char2bin[s[i]]) & ((1 << (seqLen * 2)) - 1)
                
                seqCounter[tempSeq] += 1
                if seqCounter[tempSeq] == 2:
                    ans.append(s[i - seqLen + 1: i + 1])

        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19