未分類

Repeated DNA Sequences

BitManipulation, Go, HashTable, LeetCode

Repeated DNA Sequences

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.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example:

1
2
3
4
Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",
Return:
["AAAAACCCCC", "CCCCCAAAAA"].
提示 解題應用
HashTable HashMap

Default:

1
2
3
func findRepeatedDnaSequences(s string) []string {
}

解答思路:

這題最主要是要用hashmap來儲存所有的可能，並且如果發現該字串已經存於hashmap之中才將其放入結果之中，其中key為該字串而value則是boolean值用來確定是否已放入結果陣列已避免重覆放入，而如果想要省空間的話，由於ACGT只有四種字母組成，以十進制表示的話A:101,C:0103,G:0107,T:0124會發現到剛好最後一個數字都不相同，只取最後的數字再以二進制表示的話A:001,C:011,G:111,100，如果int是用32位元儲存的話，每個字母都用上3bits剛好足夠10個字母，也就是說只要用一個int32就可以表示字串，但是因為題目沒有要求，而且這麼做會搞的相當複雜，所以就直接以字串來當key做儲存。

程式碼解說:

一開始先初始化hashmap以儲存所有可能，其中key為DNA序列而value則是boolean值用來確定是否已放入結果陣列已避免重覆放入，接著就從頭開始遍歷字串直到倒數第十個字母為止(因為每個序列最少有十個字母)，每次都從取出字母的位置往後算10個字母(包含取出的位置)當作一序列並檢查是否存在於hashmap，如果該序列存在就再檢查value值確定能否放入結果陣列之中，如果ok為false表示先前就曾出現過第二次並已存於結果中，ok為true則將字串放入結果陣列並將value值改為false，而如果該序列不存在則直接將其放入hashmap之中並將value設為true，最後待全數可能的序列遍歷完畢後才回傳整個結果陣列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var substring string
var result []string
hashMap := make(map[string]bool)
for i := 0; i < len(s)-9; i++ {
	substring = s[i : i+10]
	ok, exist := hashMap[substring]
	if exist && ok {
		result = append(result, substring)
		hashMap[substring] = false
	} else if !exist {
		hashMap[substring] = true
	}
}
return result

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func findRepeatedDnaSequences(s string) []string {
	var substring string
	var result []string
	hashMap := make(map[string]bool)
	for i := 0; i < len(s)-9; i++ {
		substring = s[i : i+10]
		ok, exist := hashMap[substring]
		if exist && ok {
			result = append(result, substring)
			hashMap[substring] = false
		} else if !exist {
			hashMap[substring] = true
		}
	}
	return result
}

總結:

一字串表示DNA只由ACGT組成，其中每個序列由10個字母組成，找出重覆2次(含)以上的序列，最主要是要用hashmap來儲存所有的可能，並且如果發現該字串已經存於hashmap之中才將其放入結果之中，其中key為該字串而value則是boolean值用來確定是否已放入結果陣列已避免重覆放入。

分享到