2023-10-30 13:03:18 +0000 UTC

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

    bank = append(bank, startGene)

    isMut := func (gene1 string, gene2 string) bool {
        foundDiff := false
        for i := 0; i < len(gene1); i++ {
            if gene1[i] == gene2[i] {
                continue
            }
            if foundDiff {
                return false
            }
            foundDiff = true
        } 
        return foundDiff
    }

    graph := map[string][]string{}

    for i, gene1 := range bank {
        for _, gene2 := range bank[i+1:] {
            if !isMut(gene1, gene2) {
                continue
            }
            if _, ok := graph[gene1]; !ok {
                graph[gene1] = []string{}
            }
            if _, ok := graph[gene2]; !ok {
                graph[gene2] = []string{}
            }
            graph[gene1] = append(graph[gene1], gene2)
            graph[gene2] = append(graph[gene2], gene1)
        }
    }

    queue, ok := graph[endGene]
    if !ok {
        return -1
    }
    delete(graph, endGene)
    num := 1
    for length := len(queue); length > 0; length = len(queue) {
        for i := 0; i < length; i++ {
            gene := queue[i]
            muts, ok := graph[gene]
            if !ok {
                continue
            }
            if gene == startGene {
                return num 
            }
            delete(graph, gene)
            queue = append(queue, muts...)
        }
        num += 1
        queue = queue[length:]
    }

    return -1
}