© Warren Keelan

LeetCode 28. 433. Minimum Genetic Mutation

LeetCode Notes [50]: Kotlin Solution using BFS

Problem

Minimum Genetic Mutation - LeetCode

Implementation

class Solution {
        fun minMutation(startGene: String, endGene: String, bank: Array<String>): Int {
        val map = buildBank(bank, mapOf())
        val Q: Queue<Pair<String, Int>> = LinkedList()
        val visited = mutableSetOf<String>()
        Q.add(startGene to 0)

        while (Q.isNotEmpty()) {
            for (j in Q.indices) {
                val mutations = Q.poll()
                val lastGene = mutations.first
                val currentDepth = mutations.second
                if (lastGene == endGene) {
                    return currentDepth
                }
                visited.add(lastGene)
                for (i in lastGene.indices) {
                    val mutation = lastGene.substring(0, i) + "-" + lastGene.substring(i + 1, lastGene.length)
                    map[mutation]?.forEach {
                        if (!visited.contains(it)) {
                            Q.add(it to currentDepth + 1)
                        }
                    }
                }
            }
        }
        return -1
    }

    private fun buildBank(bank: Array<String>, map: Map<String, List<String>>): Map<String, List<String>> {
        val mutableMap = map.toMutableMap()
        bank.forEach { gene ->
            for (i in gene.indices) {
                val mutation = gene.substring(0, i) + "-" + gene.substring(i + 1, gene.length)
                mutableMap.putIfAbsent(mutation, listOf())
                mutableMap[mutation] = mutableMap[mutation]!! + gene
            }
        }
        return mutableMap
    }
}

Complexity Analysis

• Time complexity: O(B * n²+m^n * n²), where B = bank.length, n = bank[i].length, m stands for kinds of characters.

In this problem, we have n=8 and m=4. Then, there would be m^n possible nodes, because for each of the n characters, there are m options.

Building a mutation map for bank costs O(B * n²), since generating a mutation neighbor in the bank costs O(n²). There are m^n states that we could visit. At each state, we perform a for loop which iterates n times, each iteration would also perform string operations which cost O(n).

• Space complexity: O(nB+m^n)

With the same analysis as above, the space complexity would be O(nB+m^n). Building a mutation map for bank would take up O(nB) space, and then the visited set could grow to m^n size if all states are visited.

Similar Questions

LeetCode 127. Word Ladder

Reference

Minimum Genetic Mutation - LeetCode