leetcode：187. 重复的DNA序列

题目来源

• leetcode：187. 重复的DNA序列

题目描述

class Solution {
    
public:
    vector<string> findRepeatedDnaSequences(string s) {
    

    }
};

题目解析

哈希表

我们可以用一个哈希表统计 ss 所有长度为 1010 的子串的出现次数，返回所有出现次数超过 1010 的子串。

代码实现时，可以一边遍历子串一边记录答案，为了不重复记录答案，我们只统计当前出现次数为 22 的子串。

class Solution {
    
    const int L = 10;
public:
    vector<string> findRepeatedDnaSequences(string s) {
    
        vector<string> ans;
        unordered_map<string, int> cnt;
        int n = s.length();
        for (int i = 0; i <= n - L; ++i) {
    
            string sub = s.substr(i, L);
            if (++cnt[sub] == 2) {
    
                ans.push_back(sub);
            }
        }
        return ans;
    }
};

一定要用unordered_map，CPP的unordered_map就不需要再将字符串转hash值了

前缀树优化

class Solution {
    
    struct Trie{
    
        int cnt;
        std::vector<Trie *> vec;

        Trie(){
    
            cnt = 0;
            vec.resize(26);
        }
    };

    bool buildTrie(std::string &s, int start, Trie * root){
    
        Trie *node = root;
        for (int i = start; i < start + 10; ++i) {
    
            int c = s[i] - 'A';
            if(node->vec[c] == nullptr){
    
                node->vec[c] = new Trie();
            }
            node = node->vec[c];
        }


        bool flag = false;
        node->cnt++;
        if(node->cnt == 2){
    
            flag = true;
        }


        return flag;
    }
public:
    vector<string> findRepeatedDnaSequences(string s) {
    
        int N = s.size();
        vector<string> ans;
        Trie *root = new Trie();
        for (int i = 0; i < N - 9; ++i) {
    
            if(buildTrie(s, i, root)){
    
                ans.push_back(s.substr(i, 10));
            }
        }
        return ans;
    }
};