Leetcode 187.重复的DNA序列

重复的DNA序列

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

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

示例:

输入: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

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

思路：将字符串中所有长度为10的子串以及出现的次数用map保存，但是需要消耗很大的空间。

考虑到只有4中可能的字符A,C,G,T;可以对字符进行编码，用2bit来表示一个字符，一个含有10个字符的子串只要20bit就能表示，用一个int类型就能表示。

总长度为n的字符串，可能的子串共有n-9种，因此最多用n-9个int就能表示所有的字符组合。最坏的情况下，20bit共有2^20中组合，即1024*1024，

一个int类型4byte,因此额外消耗4MB的二外空间。

 1 class Solution {
 2     public List<String> findRepeatedDnaSequences(String s) {
 3         List<String> list = new ArrayList<String>();
 4         if(s.length() < 10)    return list;
 5         Map<Integer, Integer> map = new HashMap<Integer, Integer>();
 6         for(int i=10; i<=s.length(); i++) {
 7             int result = 0;
 8             for(int j=i-10, k=0; j<i; j++,k++) {
 9                 char c = s.charAt(j);
10                 int num = 0;
11                 switch(c) {
12                     case 'A': num = 0; break;
13                     case 'C': num = 1; break;
14                     case 'G': num = 2; break;
15                     case 'T': num = 3; break;
16                 }
17                 result += (num << 2*(9-k));
18             }
19             if(map.containsKey(result) && map.get(result) == 0) {
20                 list.add(s.substring(i-10, i));
21                 map.put(result, 1);
22             } else if(!map.containsKey(result))
23                 map.put(result, 0);
24         }
25         return list;
26     }
27 }