187. 重复的DNA序列

问题187 重复的DNA序列 ★★★☆☆

https://leetcode-cn.com/problems/repeated-dna-sequences/

在知晓题目主标签是sliding window的条件下，还是比较容易想到通过滑动窗口来降低计算成本。但是具体怎样将一个固定长度的子串映射为某个特征值呢？一开始我想的是把这个子串当作一个26进制的数来计算，但是很快发现溢出问题。后面参考了官方题解才想到，为了保证计算速度，往2进制靠拢才是正确思路。

直接计算子串的哈希值，然后判断是否相同子串，这样可以吗？理论上，这样是不可以的，因为可能出现哈希碰撞，即相同子串的哈希值相等，但哈希值相等的子串不一定是相同子串。

另外，为什么题目背景是DNA序列呢？把字符串限定在由ACGT组成，其实就是为了简化二进制编码，只需要2位二进制位就可以完成对ACGT的编码。其实，即便题目放开为全部英文字母，这个题目的解决方法也是一样的，无非是需要5位二进制位才能编码26个英文字母。

	private Map<Character, Integer> map = new HashMap<Character, Integer>() {{
		put('A', 0b00);
		put('C', 0b01);
		put('G', 0b10);
		put('T', 0b11);
	}};

	public List<String> findRepeatedDnaSequences(String s) {
		if (s == null) {
			return Collections.emptyList();
		}

		int len = s.length();
		if (len <= 10) {
			return Collections.emptyList();
		}

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

		Map<Integer, Integer> cnt = new HashMap<>();

		int hash = 0;
		for (int i = 0; i < 10; i++) {
			hash = hash << 2 | map.get(s.charAt(i));
		}
		cnt.put(hash, 1);

		for (int i = 1; i <= len - 10; i++) {
			char in = s.charAt(i + 9);
			hash = hash << 2 | map.get(in);
			hash = hash & 0b00000000000011111111111111111111;

			cnt.put(hash, cnt.getOrDefault(hash, 0) + 1);

			if (cnt.get(hash) == 2) {
				ret.add(s.substring(i, i + 10));
			}
		}

		return ret;
	}

在 LeetCode 查看