Open Zheaoli opened 1 year ago
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;
};
2022-11-05