重复的DNA序列

[louzhedong]

习题

出处 LeetCode 算法第187题

所有 DNA 由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。

编写一个函数来查找 DNA 分子中所有出现超多一次的10个字母长的序列（子串）。

示例:

输入: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

输出: ["AAAAACCCCC", "CCCCCAAAAA"]

思路

遍历所有10个字符的组合，并将其当做key存于map中，找出其中value对于1的即可

解答

JavaScript

var findRepeatedDnaSequences = function (s) {
  var length = s.length, map = {}, result = [];

  for (var i = 0; i <= length - 10; i++) {
    var temp = s.slice(i, i + 10);
    if (map[temp]) {
      map[temp]++;
    } else {
      map[temp] = 1;
    }
  }

  for (var key in map) {
    if (map[key] > 1) {
      result.push(key);
    }
  }

  return result;
};

Java

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        int length = s.length();
        Map<String, Integer> map = new HashMap<>();
        List<String> result = new ArrayList<>();

        for (int i = 0; i <= length - 10; i++) {
            String temp = s.substring(i, i + 10);
            if (map.containsKey(temp)) {
                map.put(temp, map.get(temp) + 1);
            } else {
                map.put(temp, 1);
            }
        }

        for (String key : map.keySet()) {
            if (map.get(key) > 1) {
                result.add(key);
            }
        }
        return result;
    }
}