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