【LeetCode】187. Repeated DNA Sequences
LeetCode dna sequences
2023-09-11 14:20:27 时间
Repeated DNA Sequences
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"].
每个长度为10的字符串，通过查找map，判断之前是否出现过。
用hash可以降低空间复杂度。
class Solution { public: vector<string> findRepeatedDnaSequences(string s) { vector<string> ret; if(s.size() < 10) return ret; unordered_map<size_t, int> m; hash<string> strh; for(int i = 0; i <= s.size()-10; i ++) { string sub = s.substr(i, 10); m[strh(sub)] ++; if(m[strh(sub)] == 2) {//find repeat ret.push_back(sub); } } return ret; } };
相关文章
- Java实现 LeetCode 面试题62. 圆圈中最后剩下的数字（约瑟夫环）
- Java实现 LeetCode 539 最小时间差（单位转换）
- Java实现 LeetCode 481 神奇字符串
- Java实现 LeetCode 459 重复的子字符串
- Java实现 LeetCode 441 排列硬币
- Java实现 LeetCode 378 有序矩阵中第K小的元素
- Java实现 LeetCode 241 为运算表达式设计优先级
- Java实现 LeetCode 136 只出现一次的数字
- [LeetCode] Search a 2D Matrix II
- LeetCode（87）：扰乱字符串
- LeetCode-998. 最大二叉树 II【最大二叉树】
- Leetcode 338. 比特位计数
- Leetcode 896. 单调数列
- 【LeetCode】Repeated DNA Sequences 解题报告
- 【Mac系统】Vscode使用LeetCode插件报错‘leetcode.toggleLeetCodeCn‘ not found
- LeetCode 430. 扁平化多级双向链表