题目：

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.
Example：

Input：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output：["AAAAACCCCC", "CCCCCAAAAA"]

思路1：

看到本题之后首先想到的思路是利用Java字符串附带的indexOf和lastIndexOf。取出每个10位字符串分别判断在给定字符串s中首先出现和最后出现的位置是否为一个，不是一个位置则加入到结果中。

不过很可惜，使用此方法后Time Limit Exceeded.

上网查资料后，了解到了一个很妙的解法。
首先设两个Set，分别取名为firsttime和secondtime.思路依然是取10位字符串，首先加入到firsttime。

Set的add方法可以返回布尔类型。加入成功返回true，否则返回false.

这样在第二次加入同样的字符串时firsttime将返回false.此时将此字符串加入到secondtime中，即为结果。

代码：

public List<String> findRepeatedDnaSequences(String s) {
        List<String>result = new ArrayList<String>();
        if(s == null || s.length() == 0)
            return result;
        Set<String>set = new HashSet<String>();
        Set<String>visit = new HashSet<String>();
        for(int i=0;i<s.length()-9;i++){
            String substr = s.substring(i, i+10);
            if(!visit.add(substr)){
                set.add(substr);
            }
        }
        return new ArrayList<String>(set);
}

思路2：

上面的方法解题虽然很妙但是却存在着一个巨大的缺点。因为系统不得不开n-9个String来存储中间结果。可能会造成溢出。

上网查询之后发现了另一种更妙的方法。由于题目要求给定的字符串中只能有A、C、G、T.我们可以设A为00，C为01, G为10，T为11.

这样设置有一个好处就是每个字母都是两位，题目要的是长度为10的字符串，这样字符串的位数就是20，小于Int所能表示的数字的最长位数32.

在每次截取给定字符串s的时候设置一个正整数0，每次循环向左移动两位。在和循环到的字符做一个或操作。这样10位循环结束后将得到一个十位字符所表示的整数。

设置两个Set分别取名为firsttime何secondtime.和上述思路一样一旦firsttime中已经有了之前存取的整数，则代表这个位置上的字符串是满足题目要求的。

代码：

public List<String> findRepeatedDnaSequences2(String s){
        List<String>result = new ArrayList<String>();
        if(s == null || s.length() == 0)
            return result;
        Set<Integer>firsttime = new HashSet<Integer>();
        Set<Integer>secondtime = new HashSet<Integer>();
        Map<Character, Integer>map = new HashMap<Character, Integer>();
        map.put('A', 0);
        map.put('C', 1);
        map.put('G', 2);
        map.put('T', 3);
        for(int i=0;i<s.length()-9;i++){
            int value = 0;
            for(int j=i;j<i+10;j++){
                value <<= 2;
                value |= map.get(s.charAt(j));
            }
            if(!firsttime.add(value) && secondtime.add(value)){
                result.add(s.substring(i, i+10));
            }
        }
        return result;
}