【题目】
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"].
【解析】
题意：找出DNA序列中所有出现次数大于1的长度为10的子串。
我觉得题目给的例子有问题，例子中除了给出的两个子串，还有“ACCCCCAAAA", "AACCCCCAAA", "AAACCCCCAA", "AAAACCCCCA"也都符合条件。
参考https://oj.leetcode.com/discuss/24478/i-did-it-in-10-lines-of-c 我来解释一下思路：
首先看这道题的Tags是Hash Table和Bit Manipulation，那么如何把字符串转化为位操作呢？我们首先来看字母 ”A" "C" “G" "T" 的ASCII码，分别是65, 67, 71, 84，二进制表示为1000001,1000011,1000111,1010100。可以看到它们的后四位是不同，所以用后四位就可以区分这四个字母。一个字母用3bit来区分，那么10个字母用30bit就够了。用int的第29~0位分表表示这0~9个字符，然后把30bit转化为int作为这个子串的key，放入到HashTable中，，以判断该子串是否出现过。
【Java代码】
public class Solution {public List<String> findRepeatedDnaSequences(String s) {List<String> ans = new ArrayList<String>();HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();int key = 0;for (int i = 0; i < s.length(); i++) {key = ((key << 3) | (s.charAt(i) & 0x7)) & 0x3fffffff;if (i < 9) continue;if (map.get(key) == null) {map.put(key, 1);} else if (map.get(key) == 1) {ans.add(s.substring(i – 9, i + 1));map.put(key, 2);}}return ans;}}
发光并非太阳的专利，你也可以发光
