leetcode-go/leetcode/medium/433.minimum-genetic-mutation.go

func minMutation(start string, end string, bank []string) int {
	src, dst := -1, -1
	for i := range bank {
		if bank[i] == start {
			src = i
		} else if bank[i] == end {
			dst = i
		}
	}
	if dst == -1 {
		return -1
	} else if src == dst {
		return 0
	}
	if src == -1 {
		bank = append(bank, start)
		src = len(bank) - 1
	}
	n := len(bank)
	dist := make([]int, n)
	queue := []int{src}
	for len(queue) != 0 { // BFS
		cur := queue[0]
		queue = queue[1:]
		for i := 0; i < n; i++ {
			if i != cur && dist[i] == 0 && isMutable(bank[cur], bank[i]) {
				dist[i] = dist[cur] + 1
				queue = append(queue, i)
			}
		}
		if dist[dst] != 0 {
			return dist[dst]
		}
	}
	return -1
}

func isMutable(a, b string) bool {
	cnt := 0
	for i := range a {
		if a[i] != b[i] {
			cnt++
		}
	}
	return cnt == 1
}