Rolling hash AC Python solution.


  • 4
    M
    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

  • 0

    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)
    

  • 0
    L

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


Log in to reply
 

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