力扣(LeetCode)187.重复的DNA序列(C++）

哈希表

直观思考，由于限定了答案长度 10 10 10 ，只需要一次遍历字符串，统计所有长度为 10 10 10 的子串的出现次数(哈希表) ，最后遍历哈希表，维护答案，记录出现 2 2 2 次(及以上)的字符串 。

class Solution { public: vector<string> findRepeatedDnaSequences(string s) { unordered_map<string,int> mp; for(int i = 0;i+10<=s.size();i++) mp[s.substr(i,10)]++; vector<string> ans; for(auto &[S,V]:mp) if(V>=2) ans.push_back(S); return ans; } };

时间复杂度 : O ( n × ∣ C ∣ ) O(n\times |C|) O(n×∣C∣) ， 字符串长度 n n n ， 核苷酸长度 ∣ C ∣ = 10 |C|=10 ∣C∣=10 ，一边遍历字符串，统计每个长度为 10 10 10 的子串，时间复杂度 O ( n × ∣ C ∣ ) O(n\times |C|) O(n×∣C∣) 。

空间复杂度 : O ( n × ∣ C ∣ ) O(n\times |C|) O(n×∣C∣) ， 哈希表的最坏空间复杂度 O ( n × ∣ C ∣ ) O(n\times |C|) O(n×∣C∣) 。

字符串哈希

给定一个字符串，判断两个子串是否相同的问题 ，更为高效的做法是字符串哈希 : 将字符串的每一位看做 P P P 进制数，整个字符串就是个很大的 P P P 进制数 。判断某两个子串是否相同，转化为判断整个子串对应的数字是否相同。类比十进制考虑。

class Solution { public: // ULL get(int l,int r){ // return h[r] - h[l]*p[r-l+1]; // } vector<string> findRepeatedDnaSequences(string s) { const int P = 13331; const int N = s.size() + 1; typedef unsigned long long ULL; unordered_map<ULL,int> mp; vector<string> ans; ULL h[N], p[N]; h[0] = 0,p[0] = 1; for(int i = 1;i<N;i++){ h[i] = h[i-1]*P + s[i-1]; p[i] = p[i-1]*P; } for(int i = 10;i<N;i++){ ULL hash_val = h[i] - h[i-10]*p[10]; mp[hash_val]++; if(mp[hash_val]==2) ans.push_back(s.substr(i-10,10)); } return ans; } };

时间复杂度 : O ( n ) O(n) O(n) ， 字符串长度 n n n ， 只进行常数次遍历，时间复杂度 O ( n ) O(n) O(n) 。

空间复杂度 : O ( n ) O(n) O(n) ， 哈希表的空间复杂度 O ( n ) O(n) O(n) 。

AC

致语 理解思路很重要！欢迎读者在评论区留言，墨染看到就会回复的。