LeetCode刷题——重复的DNA序列#187#Medium

重复的DNA序列的思路探讨与源码
    重复的DNA序列的题目如下图，该题属于字符串和哈希表类型的题目，主要考察对于哈希表的使用和字符串滑窗方法的理解。本文的题目作者想到2种方法，分别是滑动窗口方法和位运算方法，其中滑动窗口方法使用Java进行编写，而位运算方法使用Python进行编写，当然这可能不是最优的解法，还希望各位大佬给出更快的算法。

    本人认为该题目可以使用滑动窗口的思路进行解决，首先计算字符串的长度，并且初始化一个结果列表与一个哈希Map。然后开始循环遍历字符串，用字符串的子串的方法将结果提取出来，然后把这段字串的值作为KEY值去哈希Map里判断是否有该值，如果有就将这个重复的子字符串添加到结果列表里，否则就把这个子字符串放到那个哈希Map里为下一次遇到相同的字符串做准备。并且循环结束后最终返回结果列表。那么按照这个思路我们的Java代码如下：

#喷火龙与水箭龟class Solution { public List findRepeatedDnaSequences(String s) { int lenStr = s.length(); List resFinal = new ArrayList<>(); Map saveMap = new HashMap<>(); for (int jr = 0; jr + 10 <= lenStr; jr++) { String ind = s.substring(jr,jr+10); int nbx = saveMap.getOrDefault(ind,0); if(nbx == 1){ resFinal.add(ind); } saveMap.put(ind,nbx+1); } return resFinal; }}

    显然，我们看到滑动窗口的效果还行，同时还可以使用位运算的方法解决。首先将DNA序列的A、C、G、T四个值分别转化为0、1、2、3，其实就是A用二进制的00、C用二进制的01、G用二进制的10、T用二进制的11表示。然后初始化参数并计算字符串长度，如果字符串长度小于10，那么就无需后续遍历，直接返回空列表即可。同时将结果列表进行初始化，并设置一个默认值返回0的空字典。然后开始遍历，将子字符串通过唯一的整数进行表示，然后再去判断这个整数是否在字典里出现过，如果是就直接将字符串插入到结果列表里。最终循环结束并返回结果列表。所以按照这个思路就可以解决，下面是Python代码：

#喷火龙与水箭龟class Solution: def findRepeatedDnaSequences(self, s: str) -> List[str]: stdMap = {'A':0,'C':1,'G':2,'T':3} stdLen = 10 strLen = len(s) if(strLen<=stdLen): return [] resFinal = [] ind = 0 dfx = defaultdict(int) for jr in s[:stdLen-1]: ind = (ind << 2) | stdMap[jr] for kr in range(strLen-stdLen+1): ind = ((ind << 2) | stdMap[s[kr+stdLen-1]]) & ((1 << (stdLen*2))-1) dfx[ind] = dfx[ind]+1 if(dfx[ind]==2): resFinal.append(s[kr:kr+stdLen]) return resFinal

    从结果来说Java版本的滑动窗口方法的效率还可以，而Python版本的位运算方法的速度比较差，但应该是有更多的方法可以进一步提速的，希望朋友们能够多多指教，非常感谢。