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版本的位运算方法的速度比较差，但应该是有更多的方法可以进一步提速的，希望朋友们能够多多指教，非常感谢。