← Static tasks

127. Word Ladder

leetcode hard

#csharp#graph#hard#hash-table#leetcode#queue#search#string#tree

Task

Секвенция трансформации от слова 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.

C# solution

matched/original
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
    public int LadderLength(string beginWord, string endWord, IList<string> wordList) {
        int L = beginWord.Length;
        Dictionary<string, List<string>> allComboDict = new Dictionary<string, List<string>>();
        foreach (string word in wordList) {
            for (int i = 0; i < L; i++) {
                string newWord = word.Substring(0, i) + '*' + word.Substring(i + 1, L - i - 1);
                if (!allComboDict.ContainsKey(newWord))
                    allComboDict[newWord] = new List<string>();
                allComboDict[newWord].Add(word);
            }
        }
        Queue<Tuple<string, int>> Q = new Queue<Tuple<string, int>>();
        Q.Enqueue(new Tuple<string, int>(beginWord, 1));
        Dictionary<string, bool> visited = new Dictionary<string, bool>();
        visited[beginWord] = true;
        while (Q.Any()) {
            var node = Q.Dequeue();
            string word = node.Item1;
            int level = node.Item2;
            for (int i = 0; i < L; i++) {
                string newWord = word.Substring(0, i) + '*' + word.Substring(i + 1, L - i - 1);
                foreach (string adjacentWord in allComboDict.GetValueOrDefault(newWord, new List<string>())) {
                    if (adjacentWord.Equals(endWord))
                        return level + 1;
                    if (!visited.ContainsKey(adjacentWord)) {
                        visited[adjacentWord] = true;
                        Q.Enqueue(new Tuple<string, int>(adjacentWord, level + 1));
                    }
                }
            }
        }
        return 0;
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int LadderLength(string beginWord, string endWord, vector<string> wordList) {
        int L = beginWord.size();
        unordered_map<string, List<string>> allComboDict = new unordered_map<string, List<string>>();
        foreach (string word in wordList) {
            for (int i = 0; i < L; i++) {
                string newWord = word.Substring(0, i) + '*' + word.Substring(i + 1, L - i - 1);
                if (!allComboDict.count(newWord))
                    allComboDict[newWord] = new List<string>();
                allComboDict[newWord].push_back(word);
            }
        }
        queue<Tuple<string, int>> Q = new queue<Tuple<string, int>>();
        Q.Enqueue(new Tuple<string, int>(beginWord, 1));
        unordered_map<string, bool> visited = new unordered_map<string, bool>();
        visited[beginWord] = true;
        while (Q.Any()) {
            var node = Q.Dequeue();
            string word = node.Item1;
            int level = node.Item2;
            for (int i = 0; i < L; i++) {
                string newWord = word.Substring(0, i) + '*' + word.Substring(i + 1, L - i - 1);
                foreach (string adjacentWord in allComboDict.GetValueOrDefault(newWord, new List<string>())) {
                    if (adjacentWord.Equals(endWord))
                        return level + 1;
                    if (!visited.count(adjacentWord)) {
                        visited[adjacentWord] = true;
                        Q.Enqueue(new Tuple<string, int>(adjacentWord, level + 1));
                    }
                }
            }
        }
        return 0;
    }
}

Java solution

matched/original
import java.util.*;

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int L = beginWord.length();
        Map<String, List<String>> allComboDict = new HashMap<>();

        wordList.forEach(word -> {
            for (int i = 0; i < L; i++) {
                String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);
                List<String> transformations = allComboDict.getOrDefault(newWord, new ArrayList<>());
                transformations.add(word);
                allComboDict.put(newWord, transformations);
            }
        });

        Queue<Pair<String, Integer>> Q = new LinkedList<>();
        Q.add(new Pair(beginWord, 1));

        Map<String, Boolean> visited = new HashMap<>();
        visited.put(beginWord, true);

        while (!Q.isEmpty()) {
            Pair<String, Integer> node = Q.remove();
            String word = node.getKey();
            int level = node.getValue();
            for (int i = 0; i < L; i++) {
                String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);

                for (String adjacentWord : allComboDict.getOrDefault(newWord, new ArrayList<>())) {
                    if (adjacentWord.equals(endWord)) {
                        return level + 1;
                    }
                    if (!visited.containsKey(adjacentWord)) {
                        visited.put(adjacentWord, true);
                        Q.add(new Pair(adjacentWord, level + 1));
                    }
                }
            }
        }

        return 0;
    }
}

JavaScript solution

matched/original
var ladderLength = function (beginWord, endWord, wordList) {
    let L = beginWord.length;
    let allComboDict = {};
    for (let word of wordList) {
        for (let i = 0; i < L; i++) {
            let newWord = word.substring(0, i) + "*" + word.substring(i + 1, L);
            if (!allComboDict[newWord]) allComboDict[newWord] = [];
            allComboDict[newWord].push(word);
        }
    }
    let Q = [[beginWord, 1]];
    let visited = { [beginWord]: true };
    while (Q.length > 0) {
        let node = Q.shift();
        let word = node[0];
        let level = node[1];
        for (let i = 0; i < L; i++) {
            let newWord = word.substring(0, i) + "*" + word.substring(i + 1, L);
            for (let adjacentWord of allComboDict[newWord] || []) {
                if (adjacentWord === endWord) {
                    return level + 1;
                }
                if (!visited[adjacentWord]) {
                    visited[adjacentWord] = true;
                    Q.push([adjacentWord, level + 1]);
                }
            }
        }
    }
    return 0;
};

Python solution

matched/original
from collections import defaultdict, deque
from typing import List

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList or not endWord or not beginWord or not wordList:
            return 0

        L = len(beginWord)
        all_combo_dict = defaultdict(list)
        for word in wordList:
            for i in range(L):
                all_combo_dict[word[:i] + "*" + word[i + 1:]].append(word)

        queue = deque([(beginWord, 1)])
        visited = {beginWord: True}
        while queue:
            current_word, level = queue.popleft()
            for i in range(L):
                intermediate_word = current_word[:i] + "*" + current_word[i + 1:]
                for word in all_combo_dict[intermediate_word]:
                    if word == endWord:
                        return level + 1
                    if word not in visited:
                        visited[word] = True
                        queue.append((word, level + 1))
                all_combo_dict[intermediate_word] = []
        return 0

Go solution

matched/original
func ladderLength(beginWord string, endWord string, wordList []string) int {
    L := len(beginWord)
    allComboDict := make(map[string][]string)
    for _, word := range wordList {
        for i := 0; i < L; i++ {
            newWord := word[:i] + "*" + word[i+1:]
            allComboDict[newWord] = append(allComboDict[newWord], word)
        }
    }
    Q := make([][]interface{}, 0, len(wordList))
    Q = append(Q, []interface{}{beginWord, 1})
    visited := make(map[string]bool)
    visited[beginWord] = true
    for len(Q) > 0 {
        node := Q[0]
        Q = Q[1:]
        word := node[0].(string)
        level := node[1].(int)
        for i := 0; i < L; i++ {
            newWord := word[:i] + "*" + word[i+1:]
            for _, adjacentWord := range allComboDict[newWord] {
                if adjacentWord == endWord {
                    return level + 1
                }
                if !visited[adjacentWord] {
                    visited[adjacentWord] = true
                    Q = append(Q, []interface{}{adjacentWord, level + 1})
                }
            }
        }
    }
    return 0
}

Explanation

Algorithm

1️⃣

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

2️⃣

Использование очереди для обхода: Поместите в очередь кортеж, содержащий

beginWord

и число 1, где 1 обозначает уровень узла. Вам нужно вернуть уровень узла

endWord

, так как он будет представлять длину кратчайшей последовательности преобразования. Используйте словарь посещений, чтобы избежать циклов.

3️⃣

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

😎