leetcode 187. Repeated DNA Sequences 求重复的DNA串 ---------- java

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example,

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

Return:

["AAAAACCCCC", "CCCCCAAAAA"].

其实就是一个字符串，然后以10个为单位，求重复两次以上的字符串。

1、用一个set就可以实现了。

public class Solution {

    public List<String> findRepeatedDnaSequences(String s) {

        List<String> list = new ArrayList();

        int len = s.length();

        if (len <= 10){

            return list;

        }

        HashSet<String> set = new HashSet();

        for (int i = 10; i <= len; i++){

            String str = s.substring(i - 10, i);

            if (set.contains(str) && !list.contains(str)){

                list.add(str);

            } else {

                set.add(str);

            }

        }

        return list;

    }

}

2、discuss里面是有一些利用位操作的，例如。

public List<String> findRepeatedDnaSequences(String s) {

    Set<Integer> words = new HashSet<>();

    Set<Integer> doubleWords = new HashSet<>();

    List<String> rv = new ArrayList<>();

    char[] map = new char[26];

    //map['A' - 'A'] = 0;

    map['C' - 'A'] = 1;

    map['G' - 'A'] = 2;

    map['T' - 'A'] = 3;

    for(int i = 0; i < s.length() - 9; i++) {

        int v = 0;

        for(int j = i; j < i + 10; j++) {

            v <<= 2;

            v |= map[s.charAt(j) - 'A'];

        }

        if(!words.add(v) && doubleWords.add(v)) {

            rv.add(s.substring(i, i + 10));

        }

    }

    return rv;

}

leetcode 187. Repeated DNA Sequences 求重复的DNA串 ---------- java的相关教程结束。