Repeated DNA Sequences

描述

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的窗口，从左到右扫描，放入 HashMap，并把计数器增一。最后，把 HashMap 中所有计数器大于1的字符串输出来。时间复杂度 O(n), 由于HashMap中存储了所有长度为10的子串，所以空间复杂度O(10n)。

由于字符串中只存在 A, C, G, T 四种字符，我们可以把每个字符映射为2个bit:

  1. A -> 00
  2. C -> 01
  3. G -> 10
  4. T -> 11

每个长度为10的字符串，可以映射为 20 bits, 小于32位，因此可以把这个字符串映射到一个整数。这个方法时间复杂度依旧是O(n)，但空间复杂度下降到了O(n)。

解法1 简单粗暴

  1. // Repeated DNA Sequences
  2. // Time Complexity: O(n), Space Complexity: O(10n)
  3. public class Solution {
  4.     public List<String> findRepeatedDnaSequences(String s) {
  5.         final List<String> result = new ArrayList<>();
  6.         if (s.length() < 10) return result;
  8.         final Map<String, Integer> counter = new HashMap<>();
  10.         for (int i = 0; i < s.length() - 9; ++i) {
  11.             final String key = s.substring(i, i + 10);
  12.             int value = counter.getOrDefault(key, 0);
  13.             counter.put(key, value + 1);
  14.         }
  16.         for (Map.Entry<String, Integer> entry : counter.entrySet()) {
  17.             if (entry.getValue() > 1) {
  18.                 result.add(entry.getKey());
  19.             }
  20.         }
  21.         return result;
  22.     }
  23. }

解法2 完美哈希

  1. // Repeated DNA Sequences
  2. // Time Complexity: O(n), Space Complexity: O(n)
  3. public class Solution {
  4.     public List<String> findRepeatedDnaSequences(String s) {
  5.         final List<String> result = new ArrayList<>();
  6.         if (s.length() < LEN) return result;
  8.         final Map<Character, Integer> charMap = new HashMap<>();
  9.         charMap.put('A', 0);
  10.         charMap.put('C', 1);
  11.         charMap.put('G', 2);
  12.         charMap.put('T', 3);
  14.         final Map<Integer, Character> intMap = new HashMap<>();
  15.         intMap.put(0, 'A');
  16.         intMap.put(1, 'C');
  17.         intMap.put(2, 'G');
  18.         intMap.put(3, 'T');
  20.         final Map<Integer, Integer> counter = new HashMap<>();
  22.         for (int i = 0; i < s.length() - LEN + 1; ++i) {
  23.             final String key = s.substring(i, i + 10);
  24.             final int hashValue = strToInt(key, charMap);
  25.             counter.put(hashValue, counter.getOrDefault(hashValue, 0) + 1);
  26.         }
  28.         for (Map.Entry<Integer, Integer> entry : counter.entrySet()) {
  29.             if (entry.getValue() > 1) {
  30.                 result.add(intToStr(entry.getKey(), intMap));
  31.             }
  32.         }
  33.         return result;
  34.     }
  36.     // perfect hash, no collisions
  37.     private static int strToInt(String s, Map<Character, Integer> charMap) {
  38.         assert s.length() == LEN;
  39.         int x = 0;
  40.         for (int i = 0; i < LEN; ++i) {
  41.             final char ch = s.charAt(i);
  42.             x = (x << 2) + charMap.get(ch);
  43.         }
  44.         return x;
  45.     }
  46.     private String intToStr(int x, Map<Integer, Character> intMap) {
  47.         final StringBuilder sb = new StringBuilder();
  49.         while (x > 0) {
  50.             final char ch = intMap.get(x & 3);
  51.             sb.append(ch);
  52.             x >>= 2;
  53.         }
  54.         while (sb.length() < LEN) sb.append(intMap.get(0));
  55.         return sb.reverse().toString();
  56.     }
  57.     private static final int LEN = 10;
  58. }

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/bitwise-operations/repeated-dna-sequences.html