433.最小基因变化

leetcode

广度优先搜索

广度优先搜索的时候，注意要去掉已遍历过的情况，方法是从bankMap中删除已遍历的元素。

时间复杂度：O(C x n x m)，其中C为基因位的可选项数量（此处为ACGT四种，C为4）， m为bank的长度，n为基因序列的长度。
空间复杂度： O(m x n)。合法性的哈希表中一共存有 m个元素，队列中最多有 mm 个元素，每个元素的空间为 O(n)。O(m + n x m) = O(m x n)

func minMutation(start string, end string, bank []string) int {
    if start == end {
        return 0
    }

    if len(bank) == 0 {
        return -1
    }

    bankMap := map[string]bool{}
    queue := []string{}

    for _, g := range bank {
        bankMap[g] = true
    }

    queue = append(queue, start)

    // 最少也进行了一次变化
    for count := 1; len(queue) != 0; count++ {
        for _, cur := range queue {
            queue = queue[1:]
            for i, x := range cur {
                for _, y := range "ACGT" {
                    if y != x {
                        cur := cur[:i] + string(y) + cur[i+1:]
                        // fmt.Printf("index: %v cur: %v\n", i, cur)
                        if _, ok := bankMap[cur]; ok {
                            if cur == end {
                                return count
                            }
                            queue = append(queue, cur)
                        
                            // 去除已经遍历过的情况 
                            delete(bankMap, cur)
                        }
                    }
                }
            }
        }
    }

    return -1

}