187. 重复的DNA序列

187. 重复的DNA序列

• 难度: medium
• 原始链接: https://leetcode.cn/problems/repeated-dna-sequences
• 标签: 哈希, 位运算

解法一: 哈希

go

func findRepeatedDnaSequences(s string) []string {
    length := len(s)
    if length < 10 {
        return []string{}
    }
    hash := map[string]int{}
    str := "0"
    ans := []string{}
    for i := 0; i < length; i++ {
        for len(str) < 10 {
            str += string(s[i])
            i++
        }
        str += string(s[i])
        str = str[1:]
        if hash[str] == 1 {
            ans = append(ans, str)
        }
        hash[str]++
    }
    return ans
}

解法二: 位运算

go

func findRepeatedDnaSequences(s string) []string {
    length := len(s)
    if length < 10 {
        return []string{}
    }
    num := 0
    dict := map[byte]int{
        'A': 0,
        'C': 1,
        'G': 2,
        'T': 3,
    }
    for i := 0; i < 10; i++ {
        num = (num << 2) | dict[s[i]]
    }
    hash := map[int]int{
        num: 1,
    }
    ans := []string{}
    for i := 10; i < length; i++ {
        num = ((num << 2) | dict[s[i]]) & ((1 << 20) - 1)
        if hash[num] == 1 {
            sb := strings.Builder{}
            for j := i - 9; j <= i; j++ {
                sb.WriteString(string(s[j]))
            }
            ans = append(ans, sb.String())
        }
        hash[num]++
    }
    return ans
}