187. Repeated DNA Sequences

题目描述和难度

  • 题目描述：

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

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

示例:

输入: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

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

思路分析

求解关键：题目中要求找一个字符串中固定长度为 10 的有重复的子串（注意：不是子序列），因此使用滑动窗口的思想，借助哈希表就能够完成。

1、直接将字符串作为键，放入哈希表； 2、考虑到这个字符串只有 4 个字符，所以每个字符最多只用 2 位编码，因此原来的长度为 10 的字符串可以编码成一个只有低位 20 位有数值的二进制整数，以此作为键放入哈希表。

参考解答

参考解答1

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

public class Solution {

    public List<String> findRepeatedDnaSequences(String s) {
        HashSet<String> seen = new HashSet<>();
        // 为了避免重复多次的情况，这里使用 Set 去除重复
        HashSet<String> repeated = new HashSet<>();

        int len = s.length();
        int begin = 0;
        int end = 10;

        StringBuilder stringBuilder = new StringBuilder(s);
        // 注意这里是等于号，因为 substring 方法的第 2 个参数是开区间的右端点，取不到
        while (end <= len) {
            String segment = stringBuilder.substring(begin, end);
            if (seen.contains(segment)) {
                repeated.add(segment);
            } else {
                seen.add(segment);
            }
            begin++;
            end++;
        }
        return new ArrayList<>(repeated);
    }

    public static void main(String[] args) {
        String s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT";
        Solution solution = new Solution();
        List<String> repeatedDnaSequences = solution.findRepeatedDnaSequences(s);
        System.out.println(repeatedDnaSequences);
    }
}

参考解答2

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

/**
 * @author liwei
 * @date 18/7/1 上午11:22
 */
public class Solution4 {

    public List<String> findRepeatedDnaSequences(String s) {
        int len = s.length();
        // 10 个字符，1 个字符编码成二进制的 2 位，所以是 20 位
        // 0x 表示十六进制，一个 f 表示 1111
        int mask = 0xfffff;
        HashSet<Integer> seen = new HashSet<>();
        HashSet<String> repeated = new HashSet<>();
        HashMap<Character, Integer> map = new HashMap<>();
        // 表示二进制 00
        map.put('A', 0);
        // 表示二进制 01
        map.put('C', 1);
        // 表示二进制 10
        map.put('G', 2);
        // 表示二进制 11
        map.put('T', 3);
        int v = 0;
        for (int i = 0; i < len; i++) {
            // 空出两位，用来存放当前遍历到的字符的编码
            v <<= 2;
            // 可以用 + 也可以用 |，& mask 的作用是把上一步左移出了 20 位的那两位抹去
            v = (v | map.get(s.charAt(i))) & mask;
            if (i < 9) {
                continue;
            }
            if (seen.contains(v)) {
                repeated.add(s.substring(i - 9, i + 1));
            } else {
                seen.add(v);
            }
        }
        return new ArrayList<>(repeated);
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0187-repeated-dna-sequences ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。