LeetCode 187. 重复的DNA序列

序列"/>

LeetCode 187. 重复的DNA序列

原题链接：/?envType=daily-question&envId=2023-11-05

用字符串哈希处理，可以在O(1)时间内查出前面是否有长度为10的相同串

时间复杂度为O(n) 空间复杂度O(n)

C++代码

class Solution {
public:typedef unsigned long long ull;const int P = 131;ull h[100000+5],p[100000+5];ull get(int l,int r){return h[r] - h[l-1]*p[r-l+1];}vector<string> findRepeatedDnaSequences(string s) {vector<string>res;unordered_map<ull,int>mp;p[0] = 1; // p^0 = 1h[0] = 0;s = " "+s;int n = s.length();for(int i=1;i<=n;i++){p[i] = p[i-1]*P;h[i] = h[i-1]*P + s[i];}int l = 1,r = 10;while(r<=n){ull key = get(l,r);if(mp[key]==1) res.push_back(s.substr(l,10));mp[key]++;l++,r++;}return res;}       
};