Word Ladder

Problem Statement

You are given two words, beginWord and endWord, and also a list of words wordList. All of the given words are of the same length, consisting of lowercase English letters, and are all distinct.

Your goal is to transform beginWord into endWord by following the rules:

  • You may transform beginWord to any word within wordList, provided that at exactly one position the words have a different character, and the rest of the positions have the same characters.
  • You may repeat the previous step with the new word that you obtain, and you may do this as many times as needed.

Return the minimum number of words within the transformation sequence needed to obtain the endWord, or 0 if no such sequence exists.

Example 1:

Input: beginWord = "cat", endWord = "sag", wordList = ["bat","bag","sag","dag","dot"]


Output: 4

Explanation: The transformation sequence is "cat" -> "bat" -> "bag" -> "sag".

Example 2:

Input: beginWord = "cat", endWord = "sag", wordList = ["bat","bag","sat","dag","dot"]


Output: 0

Explanation: There is no possible transformation sequence from "cat" to "sag" since the word "sag" is not in the wordList.

Constraints:

  • 1 <= beginWord.length <= 10
  • 1 <= wordList.length <= 100

You should aim for a solution with O((m ^ 2) * n) time and O((m ^ 2) * n) space, where n is the number of words and m is the length of the word.

You should aim for a solution with O((m ^ 2) * n) time and O((m ^ 2) * n) space, where n is the number of words and m is the length of the word.

Hint 1

Consider the given problem in terms of a graph, treating strings as nodes. Think of a way to build edges where two strings have an edge if they differ by a single character. A naive approach would be to consider each pair of strings and check whether an edge can be formed. Can you think of an efficient way? For example, consider a string hot and think about the strings that can be formed from it by changing a single letter.

Hint 2

To efficiently build edges, consider transforming each word into intermediate states by replacing one character with a wildcard, like *. For example, the word hot can be transformed into *ot, h*t, and ho*. These intermediate states act as “parents” that connect words differing by one character. For instance, *ot can connect to words like cot. For each word in the list, generate all possible patterns by replacing each character with * and store the word as a child of these patterns. We can run a BFS starting from the beginWord, visiting other words while avoiding revisiting by using a hash set.

Hint 3

When visiting a node during BFS, if the word matches the endWord, we immediately return true. Otherwise, we generate the pattern words that can be formed from the current word and attempt to visit the words connected to these pattern words. We add only unvisited words to the queue. If we exhaust all possibilities without finding the endWord, we return false.

Solution

Breadth First Search - I

from collections import deque
from typing import List


def ladder_length_bfs_1(begin_word: str, end_word: str, word_list: List[str]) -> int:
    if (end_word not in word_list) or (begin_word == end_word):
        return 0


    n, m = len(word_list), len(word_list[0])
    adj = [[] for _ in range(n)]
    word_map = {}
    for i in range(n):
        word_map[word_list[i]] = i


    for i in range(n):
        for j in range(i + 1, n):
            cnt = 0
            for k in range(m):
                if word_list[i][k] != word_list[j][k]:
                    cnt += 1
            if cnt == 1:
                adj[i].append(j)
                adj[j].append(i)


    q, res = deque(), 1
    visit = set()
    for i in range(m):
        for c in range(97, 123):
            if chr(c) == begin_word[i]:
                continue
            word = begin_word[:i] + chr(c) + begin_word[i + 1:]
            if word in word_map and word_map[word] not in visit:
                q.append(word_map[word])
                visit.add(word_map[word])


    while q:
        res += 1
        for _ in range(len(q)):
            node = q.popleft()
            if word_list[node] == end_word:
                return res
            for neighbor in adj[node]:
                if neighbor not in visit:
                    visit.add(neighbor)
                    q.append(neighbor)


    return 0

Time complexity: O(n ^ 2 * m) Space complexity: O(n ^ 2)