Примечания LeetCode [50]: решение Kotlin с использованием BFS
Проблема
Выполнение
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
}
}
Анализ сложности
- Временная сложность: O(B * n²+m^n * n²), где B =
bank.length, n =bank[i].length, m обозначает типы символов.
В этой задаче n=8 и m=4. Тогда будет m^n возможных узлов, потому что для каждого из n символов есть m вариантов.
Создание карты мутаций для bank стоит O(B * n²), поскольку создание мутации neighbor в bank стоит O(n² ). Мы можем посетить m^n штатов. В каждом состоянии мы выполняем цикл for, который повторяется n раз, каждая итерация также будет выполнять строковые операции, которые стоят O(n).
- Сложность пространства: O(nB+m^n)
При том же анализе, что и выше, пространственная сложность будет O(nB+m^n). Построение карты мутаций для bank заняло бы O(nB) пространства, а затем набор visited мог вырасти до размера m^n, если все штаты посещаются.
