433.minimum-genetic-mutation.md

433. Minimum Genetic Mutation

TODO: Review the notes + implementations

BFS

class Solution {
    fun minMutation(startGene: String, endGene: String, bank: Array<String>): Int {
        val queue = ArrayDeque<String>()
        val visited = HashSet<String>()
        var mutations = 0

        queue.addLast(startGene)
        visited.add(startGene)
        while (queue.isNotEmpty()) {
            val size = queue.size
            for (i in 0 until size) {
                val current = queue.removeFirst()
                if (current == endGene) return mutations
                val adjSet = getAdjacentSet(current, bank)
                adjSet.forEach { adj ->
                    if (!visited.contains(adj)) {
                        queue.addLast(adj)
                        visited.add(adj)
                    }
                }
            }
            mutations++
        }
        return -1
    }

    private fun getAdjacentSet(str: String, bank: Array<String>): HashSet<String> {
        val set = HashSet<String>()
        for (s in bank) {
            var diff = 0
            for (i in 0 until 8) {
                if (str[i] != s[i]) diff++
            }
            if (diff == 1) set.add(s)
        }
        return set
    }
}

fun minMutation(start: String, end: String, bank: Array<String>): Int {
    val queue = ArrayDeque<String>()
    val visited = hashSetOf<String>()
    queue.addLast(start)
    var distance = 0
    while (queue.isNotEmpty()) {
        val size = queue.size
        for (i in 0 until size) {
            val gene = queue.removeFirst()
            if (gene == end) return distance
            if (visited.contains(gene)) continue
            visited.add(gene)
            findMutations(bank, gene).forEach { adj -> 
                if (!visited.contains(adj))
                    queue.addLast(adj)
            }
        }
        distance++
    }
    return -1
}

// TODO: we can improve this logic, just list all combination of mutation and check if the combination exists in bank.
private fun findMutations(bank: Array<String>, start: String): List<String> {
    val mutations = mutableListOf<String>()
    for (str in bank) {
        if (str.length != start.length) continue
        var diff = 0
        for (i in 0 until str.length) {
            if (str[i] != start[i]) diff++
        }
        if (diff == 1) mutations.add(str)
    }
    return mutations
}

• Time Complexity: O(B * n), where B represents the size of bank and n represents the length of gene.
• Space Complexity: O(B * n).