Update repeated-dna-sequences.py

kamyu104 · web-flow · commit d58d3a99e7e6 · 2017-10-01T20:33:18.000+08:00
diff --git a/Python/repeated-dna-sequences.py b/Python/repeated-dna-sequences.py
@@ -1,6 +1,6 @@
 # Time:  O(n)
 # Space: O(n)
-#
+
 # 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.
 # 
@@ -12,17 +12,19 @@
 #
 # Return:
 # ["AAAAACCCCC", "CCCCCAAAAA"].
-import collections
 
+import collections
 
-class Solution:
-    # @param s, a string
-    # @return a list of strings
+class Solution(object):
     def findRepeatedDnaSequences(self, s):
+        """
+        :type s: str
+        :rtype: List[str]
+        """
         dict, rolling_hash, res = {}, 0, []
 
         for i in xrange(len(s)):
-            rolling_hash = rolling_hash << 3 & 0x3fffffff | ord(s[i]) & 7
+            rolling_hash = ((rolling_hash << 3) & 0x3fffffff) | (ord(s[i]) & 7)
             if rolling_hash not in dict:
                 dict[rolling_hash] = True
             elif dict[rolling_hash]:
@@ -41,6 +43,7 @@ def findRepeatedDnaSequences2(self, s):
             l.extend([s[i:i + 10]])
         return [k for k, v in collections.Counter(l).items() if v > 1]
 
+
 if __name__ == "__main__":
     print Solution().findRepeatedDnaSequences("AAAAAAAAAA")
     print Solution().findRepeatedDnaSequences("")
