[leetcode]187. Repeated DNA Sequences重复DNA序列

小咪咪 2021-11-11 01:32 238阅读 0赞

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.

Example:

Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
    
    Output: ["AAAAACCCCC", "CCCCCAAAAA"]

题意：

DNA序列里有ATCG四种，求所有长度为10，出现次数超过一次的序列。

Solution1: HashMap

1.  scan the given string,  put each 10-letter-long substring and its corresponding frequency into a map

2. looping each entrySet in the map, find if entry.getValue() > 1

![1402496-20190504070252914-1656021923.png][]

code

1 /*
     2 Time Complexity: O(n)
     3 Space Complexity: O(n)
     4 */
     5 class Solution {
     6     public List<String> findRepeatedDnaSequences(String s) {
     7         List<String> result = new ArrayList<>();
     8         // corner case
     9         if (s.length() < 10) return result;
    10         
    11         Map<String, Integer> map = new HashMap<>();
    12         for (int i = 0; i < s.length() - 9; ++i) {
    13             String key = s.substring(i, i + 10);
    14             if(map.containsKey(key)){
    15                 map.put(key, map.get(key) + 1);
    16             }else{
    17                 map.put(key, 1);
    18             } 
    19         }
    20 
    21         for (Map.Entry<String, Integer> entry : map.entrySet()) {
    22             if (entry.getValue() > 1) {
    23                 result.add(entry.getKey());
    24             }
    25         }
    26         return result;
    27     }
    28 }

转载于:https://www.cnblogs.com/liuliu5151/p/10807445.html

[1402496-20190504070252914-1656021923.png]: /images/20211109/87339a9b7d35422caba94776fad4d2a3.png