This is question of the Day from LeetCode 2021-10-8: “187. Repeated DNA Sequences”

1. Topic description

All DNA is made up of A series of nucleotides abbreviated to ‘A’, ‘C’, ‘G’ and ‘T’, such as’ ACGAATTCCG ‘. When studying DNA, it can sometimes be very helpful to identify repeated sequences in DNA.

Write a function to find all target substrings of length 10 that occur more than once in the DNA string s.

Example 1:

Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" output: [" AAAAACCCCC ", "CCCCCAAAAA"]Copy the code

Example 2:

Input: s = "AAAAAAAAAAAAA" Output: ["AAAAAAAAAA"]Copy the code

2. Answer

1. Set+ sliding window

Maintain a sliding window of length 10 and add substrings from the window to the Set. Check whether the Set exists before adding it to the Set. If it does, add it to the RES. Finally, return the result of the rescheduled RES.

const findRepeatedDnaSequences = s= > {
    const len = s.length;
    const res = [];
    If the length is less than or equal to 10, return an empty array
    if (len <= 10) return res;
    const set = new Set(a);let i = 0;
    while (i + 9 < len) {
        // Maintain a sliding window of length 10
        const str = s.slice(i, i + 10);
        // If the current window already exists in set, add res
        if (set.has(str)) res.push(str);
        // Add set to the current window
        set.add(str);
        i++;
    }
    // Array decrement
    return [...new Set(res)];
};
Copy the code

2. Map+ Slide window

Maintain a sliding window of length 10 and add substrings in the window to the Map and count them. After the slide is complete, traverse the Map and add the number greater than 1 to the RES.

const findRepeatedDnaSequences = s= > {
    const len = s.length;
    const res = [];
    If the length is less than or equal to 10, return an empty array
    if (len <= 10) return res;
    const map = new Map(a);let i = 0;
    while (i + 9 < len) {
        // Maintain a sliding window of length 10
        const str = s.slice(i, i + 10);
        // Add map count
        map.set(str, (map.get(str) || 0) + 1);
        i++;
    }
    for (const item of map) {
        // Select the number greater than 1
        if (item[1] > 1) res.push(item[0]);
    }
    return res;
};
Copy the code

---

😄 has recently created an open source repository to summarize LeetCode’s daily problems. It is currently available in C++ and JavaScript, and you are welcome to provide other language versions!

🖥️ Warehouse address: “One of the Day series”