127. Word Ladder - Explanation

Description

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

Recommended Time & Space Complexity

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.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Breadth First Search - I

Intuition

This problem can be modeled as finding the shortest path in an unweighted graph where each word is a node and edges connect words that differ by exactly one character. We precompute the adjacency list by comparing all pairs of words. BFS naturally finds the shortest path because it explores all nodes at distance k before any node at distance k+1.

Algorithm

Create a mapping from each word to its index in the word list.
Build an adjacency list by comparing all word pairs; connect words that differ by exactly one character.
Find all words that differ by one character from beginWord and add them to the BFS queue.
Process the queue level by level, incrementing the distance counter at each level.
When endWord is found, return the current distance. If the queue empties, return 0.

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

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

        for i in range(n):
            for j in range(i + 1, n):
                cnt = 0
                for k in range(m):
                    if wordList[i][k] != wordList[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) == beginWord[i]:
                    continue
                word = beginWord[:i] + chr(c) + beginWord[i + 1:]
                if word in mp and mp[word] not in visit:
                    q.append(mp[word])
                    visit.add(mp[word])

        while q:
            res += 1
            for i in range(len(q)):
                node = q.popleft()
                if wordList[node] == endWord:
                    return res
                for nei in adj[node]:
                    if nei not in visit:
                        visit.add(nei)
                        q.append(nei)

        return 0

Time & Space Complexity

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

Where $n$ is the number of words and $m$ is the length of the word.

2. Breadth First Search - II

Intuition

Instead of precomputing the entire adjacency graph, we can generate neighbors on the fly. For each word, we try replacing each character with all 26 letters. If the resulting word exists in our word set, it is a valid neighbor. This approach trades precomputation time for potentially more neighbor generation during BFS.

Algorithm

Convert the word list to a set for O(1) lookups.
Start BFS from beginWord with distance counter set to 0.
For each word in the current level, generate all possible words by changing one character at a time.
If a generated word is in the word set, add it to the queue and remove it from the set to mark as visited.
Return the distance when endWord is found, or 0 if the queue empties.

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if (endWord not in wordList) or (beginWord == endWord):
            return 0
        words, res = set(wordList), 0
        q = deque([beginWord])
        while q:
            res += 1
            for _ in range(len(q)):
                node = q.popleft()
                if node == endWord:
                    return res
                for i in range(len(node)):
                    for c in range(97, 123):
                        if chr(c) == node[i]:
                            continue
                        nei = node[:i] + chr(c) + node[i + 1:]
                        if nei in words:
                            q.append(nei)
                            words.remove(nei)
        return 0

Time & Space Complexity

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

Where $n$ is the number of words and $m$ is the length of the word.

3. Breadth First Search - III

Intuition

We can use wildcard patterns to efficiently group words that are one character apart. For each word, create patterns by replacing each character with a wildcard. Words sharing the same pattern are neighbors. This precomputation allows O(1) neighbor lookup during BFS, as we only need to check the pattern buckets.

Algorithm

For each word in the list (including beginWord), generate patterns by replacing each character with '*' and group words by these patterns.
Start BFS from beginWord, maintaining a visited set.
For the current word, generate its patterns and look up all words in corresponding pattern buckets.
Add unvisited neighbors to the queue and mark them visited.
Return the level count when endWord is reached, or 0 if unreachable.

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

        nei = collections.defaultdict(list)
        wordList.append(beginWord)
        for word in wordList:
            for j in range(len(word)):
                pattern = word[:j] + "*" + word[j + 1 :]
                nei[pattern].append(word)

        visit = set([beginWord])
        q = deque([beginWord])
        res = 1
        while q:
            for i in range(len(q)):
                word = q.popleft()
                if word == endWord:
                    return res
                for j in range(len(word)):
                    pattern = word[:j] + "*" + word[j + 1 :]
                    for neiWord in nei[pattern]:
                        if neiWord not in visit:
                            visit.add(neiWord)
                            q.append(neiWord)
            res += 1
        return 0

Time & Space Complexity

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

Where $n$ is the number of words and $m$ is the length of the word.

4. Meet In The Middle (BFS)

Intuition

Standard BFS explores exponentially more nodes as distance increases. By running two BFS searches simultaneously from beginWord and endWord, we can meet in the middle, effectively halving the search depth and dramatically reducing the search space. At each step, we expand the smaller frontier to balance the workload.

Algorithm

Initialize two queues: one from beginWord and one from endWord.
Maintain two maps tracking the distance from each end for visited words.
Always expand the smaller queue to minimize work.
For each word, generate neighbors by changing one character at a time.
If a neighbor is already visited by the other search, return the sum of both distances.
Otherwise, if unvisited by the current search, add to queue and record distance.

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList or beginWord == endWord:
            return 0
        m = len(wordList[0])
        wordSet = set(wordList)
        qb, qe = deque([beginWord]), deque([endWord])
        fromBegin, fromEnd = {beginWord: 1}, {endWord: 1}

        while qb and qe:
            if len(qb) > len(qe):
                qb, qe = qe, qb
                fromBegin, fromEnd = fromEnd, fromBegin
            for _ in range(len(qb)):
                word = qb.popleft()
                steps = fromBegin[word]
                for i in range(m):
                    for c in range(97, 123):
                        if chr(c) == word[i]:
                            continue
                        nei = word[:i] + chr(c) + word[i + 1:]
                        if nei not in wordSet:
                            continue
                        if nei in fromEnd:
                            return steps + fromEnd[nei]
                        if nei not in fromBegin:
                            fromBegin[nei] = steps + 1
                            qb.append(nei)
        return 0

Time & Space Complexity

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

Where $n$ is the number of words and $m$ is the length of the word.