Задача: 127. Word Ladder
Сложность: Hard

Секвенция трансформации от слова beginWord к слову endWord с использованием словаря wordList представляет собой последовательность слов beginWord -> s1 -> s2 -> ... -> sk, при которой:

Каждая пара соседних слов отличается ровно одной буквой.
Каждый элемент si для 1 <= i <= k присутствует в wordList. Отметим, что beginWord не обязан быть в wordList.
sk равно endWord.
Для двух слов, beginWord и endWord, и словаря wordList, верните количество слов в кратчайшей секвенции трансформации от beginWord к endWord, или 0, если такая секвенция не существует.

Пример:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.

👨‍💻 Алгоритм:

1⃣Препроцессинг списка слов: Осуществите препроцессинг заданного списка слов (wordList), чтобы найти все возможные промежуточные состояния слов. Сохраните эти состояния в словаре, где ключом будет промежуточное слово, а значением — список слов, имеющих то же промежуточное состояние.

2⃣Использование очереди для обхода: Поместите в очередь кортеж, содержащий beginWord и число 1, где 1 обозначает уровень узла. Вам нужно вернуть уровень узла endWord, так как он будет представлять длину кратчайшей последовательности преобразования. Используйте словарь посещений, чтобы избежать циклов.

3⃣Поиск кратчайшего пути через BFS (обход в ширину): Пока в очереди есть элементы, получите первый элемент очереди. Для каждого слова определите все промежуточные преобразования и проверьте, не являются ли эти преобразования также преобразованиями других слов из списка. Для каждого найденного слова, которое имеет общее промежуточное состояние с текущим словом, добавьте в очередь пару (слово, уровень + 1), где уровень — это уровень текущего слова. Если вы достигли искомого слова, его уровень покажет длину кратчайшей последовательности преобразования.

😎 Решение:

import Foundation

class Solution {
    func ladderLength(_ beginWord: String, _ endWord: String, _ wordList: [String]) -> Int {
        let L = beginWord.count
        var allComboDict: [String: [String]] = [:]

        wordList.forEach { word in
            for i in 0..<L {
                let newWord = "\(word.prefix(i))*\(word.suffix(L - i - 1))"
                var transformations = allComboDict[newWord, default: []]
                transformations.append(word)
                allComboDict[newWord] = transformations
            }
        }

        var queue: [(String, Int)] = [(beginWord, 1)]
        var visited: [String: Bool] = [beginWord: true]

        while !queue.isEmpty {
            let (word, level) = queue.removeFirst()
            for i in 0..<L {
                let newWord = "\(word.prefix(i))*\(word.suffix(L - i - 1))"

                if let adjacentWords = allComboDict[newWord] {
                    for adjacentWord in adjacentWords {
                        if adjacentWord == endWord {
                            return level + 1
                        }
                        if visited[adjacentWord] != true {
                            visited[adjacentWord] = true
                            queue.append((adjacentWord, level + 1))
                        }
                    }
                }
            }
        }

        return 0
    }
}

Ставь 👍 и забирай 📚 Базу знаний