題目

一條基因序列由一個帶有8個字元的字串表示，其中每個字元都屬於 "A", "C", "G", "T"中的任意一個。

假設我們要調查一個基因序列的變化。一次基因變化意味著這個基因序列中的一個字元發生了變化。

例如，基因序列由"AACCGGTT" 變化至 "AACCGGTA" 即發生了一次基因變化。

與此同時，每一次基因變化的結果，都需要是一個合法的基因串，即該結果屬於一個基因庫。

現在給定3個引數 — start, end, bank，分別代表起始基因序列，目標基因序列及基因庫，

請找出能夠使起始基因序列變化為目標基因序列所需的最少變化次數。如果無法實現目標變化，請返回 -1。

注意：起始基因序列預設是合法的，但是它並不一定會出現在基因庫中。

如果一個起始基因序列需要多次變化，那麼它每一次變化之後的基因序列都必須是合法的。

假定起始基因序列與目標基因序列是不一樣的。

示例 1：start: "AACCGGTT" end: "AACCGGTA" bank: ["AACCGGTA"]

返回值: 1

示例 2：start: "AACCGGTT" end: "AAACGGTA" bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"]

返回值: 2

示例 3：start: "AAAAACCC" end: "AACCCCCC" bank: ["AAAACCCC", "AAACCCCC", "AACCCCCC"]

返回值: 3

解題思路分析

1、廣度優先搜尋；時間複雜度O(n)，空間複雜度O(n)

func minMutation(start string, end string, bank []string) int {	arr := []byte{'A', 'T', 'C', 'G'}	m := make(map[string]bool)	for i := 0; i < len(bank); i++ {		m[bank[i]] = true	}	if _, ok := m[end]; ok == false {		return -1	}	res := 0	queue := make([]string, 0)	queue = append(queue, start)	for len(queue) > 0 {		res++		length := len(queue)		for i := 0; i < length; i++ {			str := queue[i]			for j := 0; j < len(str); j++ {				for k := 0; k < len(arr); k++ {					if arr[k] != str[j] {						newStr := str[:j] + string(arr[k]) + str[j+1:]						if _, ok := m[newStr]; ok {							queue = append(queue, newStr)							delete(m, newStr)						}						if newStr == end {							return res						}					}				}			}		}		queue = queue[length:]	}	return -1}

2、深度優先搜尋；時間複雜度O(n)，空間複雜度O(n)

var res intfunc minMutation(start string, end string, bank []string) int {	res = math.MaxInt32	m := make(map[string]bool)	for i := 0; i < len(bank); i++ {		m[bank[i]] = true	}	if _, ok := m[end]; ok == false {		return -1	}	dfs(start, end, 0, bank, make([]bool, len(bank)))	if res == math.MaxInt32 {		return -1	}	return res}func dfs(start string, end string, index int, bank []string, visited []bool) {	if start == end {		if index < res {			res = index		}		return	}	for i := 0; i < len(bank); i++ {		if visited[i] == false && judge(start, bank[i]) {			visited[i] = true			dfs(bank[i], end, index+1, bank, visited)			visited[i] = false		}	}}func judge(a, b string) bool {	count := 0	for i := 0; i < len(a); i++ {		if a[i] != b[i] {			count++		}	}	return count == 1}

3、雙向廣度優先搜尋；時間複雜度O(n)，空間複雜度O(n)

func minMutation(start string, end string, bank []string) int {	arr := []byte{'A', 'T', 'C', 'G'}	m := make(map[string]bool)	for i := 0; i < len(bank); i++ {		m[bank[i]] = true	}	if _, ok := m[end]; ok == false {		return -1	}	res := 0	queueA := make([]string, 0)	queueA = append(queueA, start)	queueB := make([]string, 0)	queueB = append(queueB, end)	for len(queueA) > 0 {		res++		if len(queueA) > len(queueB) {			queueA, queueB = queueB, queueA		}		length := len(queueA)		for i := 0; i < length; i++ {			str := queueA[i]			for j := 0; j < len(str); j++ {				for k := 0; k < len(arr); k++ {					if arr[k] != str[j] {						newStr := str[:j] + string(arr[k]) + str[j+1:]						if _, ok := m[newStr]; ok {							queueA = append(queueA, newStr)							delete(m, newStr)						}						for l := 0; l < len(queueB); l++ {							if newStr == queueB[l] {								return res							}						}					}				}			}		}		queueA = queueA[length:]	}	return -1}

總結

Medium題目，可以採用廣度優先搜尋，也可以使用深度優先搜尋