# Rolling hash AC Python solution.

• ``````class Solution:
# @param s, a string
# @return a list of strings
def findRepeatedDnaSequences(self, s):
repeatSeq = set()
addedSeq = set()
result = []
answer = []
charToBin = {'A' : 0b00, 'T' : 0b01, 'G' : 0b10, 'C' : 0b11}
mask = 0xfffff
current = 0
for i in range(len(s)):
#create bit
x = charToBin[s[i]]
current |= x
if i >= 9:
if current in repeatSeq:
if current not in addedSeq:
addedSeq.add(current)
result.append(i - 9)
else:
repeatSeq.add(current)
#shift
current <<= 2
#mask
current &= mask
for i in result:
answer.append(s[i : i + 10])
return answer``````

• Same idea, but shorter solution

``````class Solution(object):
def findRepeatedDnaSequences(self, s):
repeat, add = set(), set()
charToBin = {'A':0b00, 'T':0b01, 'G': 0b10, 'C':0b11}
mask = 0xfffff
cur = 0
for i in range(len(s)):
x = charToBin[s[i]]
cur |= x
if i >= 9:
if cur not in add:
add.add(cur)
else:
repeat.add(s[i-9:i+1])
cur <<= 2
cur &= mask
return list(repeat)
``````

• @raydai can you explain the curr<<=2 part?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.