2022-11-05

[Zheaoli]

2022-11-05

[thorseraq]

187. 重复的DNA序列

function findRepeatedDnaSequences(s: string): string[] {
    const n = s.length;
    const ans: string[] = [];
    type DNA = "A" | "C" | "G" | "T";
    const map = {
        "A": 0,
        "C": 1,
        "G": 2,
        "T": 3
    };
    const cnt = new Map<number, number>();
    let window = 0;
    for (let i = 0; i < 9; i++) {
        window |= map[s.charAt(i) as DNA];
        window <<= 2;
    }
    for (let i = 9; i < n; i++) {
        window |= map[s.charAt(i) as DNA];
        cnt.set(window, (cnt.get(window) || 0) + 1);
        if (cnt.get(window) === 2) {
            ans.push(s.substring(i - 9, i + 1));
        }
        window <<= 2;
        window &= 0xfffff;
    }

    return ans;
};