Word Ladder II

Problem Id: 126 Difficulty: Hard Tag: Array Tag: String Tag: Backtracking Tag: Breadth-first Search


Intuition

If two words is only has one letter different, then we could change from one to another. And we could treat this relationship as a link. So all the word from the list contruct a graph. So this problem could be solved by 2 steps.

  1. Construct the graph, get the adjancent list.
  2. Do a BFS to get the distance from the start node to each node.
  3. Back track to get all possible path.

For the second part, the time complexity is O(n + l) where n is the number of words and l is the number of connections.

For the first part, there could be multiple ways to contruct the graph. One way is for every pair of words, check if they are linked. The time complexity of this way is O(n ^ 2 * m), where m is the length of the words. And another way it to setup a dictionary to save all words and their indexes. Then, for each word, check all possible connected words if they are in the dictionary. The time complexity of this way is O(n * m * 26 * m) = O(n * m ^ 2).

I assume that the word length is smaller than the number of words in the list, so I use the second way to construct the graph.

Solution


import string
from collections import deque


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

        wordList.append(beginWord)
        n = len(wordList)
        wordIndexes = {}
        for i, w in enumerate(wordList):
            wordIndexes[w] = i

        # Construct the graph
        adj = [set() for _ in range(n)]
        for i, w in enumerate(wordList):
            for j in range(len(w)):
                for c in string.ascii_lowercase:
                    if w[j] == c:
                        # No self loop
                        continue
                    tmp = w[:j] + c + w[j + 1:]
                    if tmp in wordIndexes:
                        k = wordIndexes[tmp]
                        adj[i].add(k)
                        adj[k].add(i)

        # The first element of each node in parent is the minimum length to
        # reach it.
        distance = [float('inf')] * n
        distance[n - 1] = 0
        queue = deque([n - 1])
        while queue:
            current = queue.popleft()
            for child in adj[current]:
                if distance[child] <= distance[current] + 1:
                    continue
                distance[child] = distance[current] + 1
                queue.append(child)

        # Back tracking to get all the paths
        target = wordIndexes[endWord]
        ans = []
        path = []
        self._dfs(n - 1, 0, adj, distance, path, ans, target)

        # Convert indexes to words
        for row in ans:
            for i in range(len(row)):
                row[i] = wordList[row[i]]
        return ans

    def _dfs(self, node, depth, adj, distance, path, ans, target):
        if distance[node] != depth:
            return
        path.append(node)
        if target == node:
            ans.append(path[:])
        else:
            for child in adj[node]:
                self._dfs(child, depth + 1, adj, distance, path, ans, target)
        path.pop()
        return