187. 重复的DNA序列（JS实现）

た入场券 2022-11-25 11:40 128阅读 0赞

## 1 题目 ##

> 所有 DNA 都由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。  
> 编写一个函数来查找目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。  
> 示例：  
> 输入：s = “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT”  
> 输出：\[“AAAAACCCCC”, “CCCCCAAAAA”\]

链接：https://leetcode-cn.com/problems/repeated-dna-sequences

## 2 思路 ##

**这道题思路很简单，就是利用哈希表来记录遇到子串的次数，但每次计算hash值时，可以使用Rabin-Karp 旋转哈希算法根据上个子串的hash在O（1）的时间内计算下一个子串的hash**

## 3代码 ##

/** * @param {string} s * @return {string[]} */
    var findRepeatedDnaSequences = function(s) { 
        let result = [];
        if (s.length <= 10) return result;
    
        let map = { 'A': 0, 'C': 1, 'G': 2, 'T': 3};
        let map1 = { };
        let tempNum = Math.pow(4, 9);
    
        let txtHash = computeHash(s, 0, 10);    //计算首次hash值
    
        for (let i=0; i<=s.length-10; i++) { 
            if (i !==0 ) txtHash = (txtHash - map[s[i-1]] * tempNum) * 4 + map[s[i+9]];   //根据上次子串hash推导当前子串的hash
            if (!map1[txtHash]) { 
                map1[txtHash] = 1;
            } else if (map1[txtHash] === 1) { 
                result.push(s.substr(i, 10));
                map1[txtHash]++;
            }
        }
    
        function computeHash(s, start, len) {    
            let hash = 0;
            for (let i=0; i<len; i++) { 
                hash += map[s[i+start]] * Math.pow(4, len - i - 1);
            }
            return hash;
        }
    
        return result;
    };