Word Ladder

The problem description can be found in LeetCode.

Approach

Again, we have another form of implicit Graph,Graph.

Once we build our adjacency list, we can perform a simple BFS starting from beginWord to endWord. A BFS traversal will help us in calculating the minimum path between these two nodes (if any).

The tricky part would be to derive or Adjacency List. In fact, assuming that all the strings in wordList have the same length, we can consider two strings to be neighbors if they differ only by one character at most.

Building such Adjacency List would require $O(n^{2}m)$, where $n$ is the size of wordList and $m$ is the unique length of each word in wordList (as per the problem requirements).

from collections import deque
from typing import Dict, List, Tuple


class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        graph = self.get_adjacency_list(beginWord, wordList)

        return self.bfs(graph, beginWord, endWord)

    def bfs(self, graph: Dict[str, List[str]], beginWord: str, endWord: str) -> int:
        queue = deque([beginWord])
        visited = {beginWord}
        ans = 1

        while queue:
            for _ in range(len(queue)):
                node = queue.popleft()
                if node == endWord:
                    return ans

                for neighbor in graph[node]:
                    if neighbor in visited:
                        continue

                    queue.append(neighbor)
                    visited.add(neighbor)

            ans += 1

        return 0

    def get_adjacency_list(
        self, beginWord: str, wordList: List[str]
    ) -> Dict[str, List[str]]:
        if beginWord not in wordList:
            wordList.append(beginWord)

        graph: Dict[str, List[str]] = {word: [] for word in wordList}
        for i in range(len(wordList)):
            word1 = wordList[i]
            for j in range(i + 1, len(wordList)):
                word2 = wordList[j]
                diff_chars = sum(
                    int(char1 != char2) for char1, char2 in zip(word1, word2)
                )

                if diff_chars <= 1:
                    graph[word1].append(word2)
                    graph[word2].append(word1)

        return graph

Although this approach is valid, it is not enough to solve the problem in LeetCode. In fact, we would get a Time Limit Exceeded error.

To overcome this solution, we have to think about a more optimized way to build the Adjacency List, which is the bottleneck of the previous approach.

A trick consists in using a pattern for each word. This pattern will be used as the key of the adjacency list and the value would be the actual string.

For example, for the beginWord hit we would have:

adj_list = {
    "*it": "hit"
    "h*t": "hit"
    "hi*": "hit"
}

This would significantly reduce the complexity as per the requirements:

• $1\le m\le 10$
• $1\le n\le 5000$

Solution

from collections import defaultdict, deque
from typing import Dict, Generator, List


class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        graph = self.get_adjacency_list(beginWord, wordList)

        return self.bfs(graph, beginWord, endWord)

    def bfs(self, graph: Dict[str, List[str]], beginWord: str, endWord: str) -> int:
        queue = deque([beginWord])
        visited = {beginWord}
        ans = 1

        while queue:
            for _ in range(len(queue)):
                word = queue.popleft()
                if word == endWord:
                    return ans

                for pattern in self.get_pattern_strings(word):
                    for neighbor in graph[pattern]:
                        if neighbor in visited:
                            continue

                        queue.append(neighbor)
                        visited.add(neighbor)

            ans += 1

        return 0

    def get_adjacency_list(
        self, beginWord: str, wordList: List[str]
    ) -> Dict[str, List[str]]:
        if beginWord not in wordList:
            wordList.append(beginWord)

        graph = defaultdict(list)

        for word in wordList:
            for pattern in self.get_pattern_strings(word):
                graph[pattern].append(word)

        return graph

    def get_pattern_strings(self, s: str) -> Generator[str, None, None]:
        return (f"{s[:i]}*{s[i+1:]}" for i in range(len(s)))

Complexity

• Time: $O(n{m}^2)$
• Space: $O(n{m}^2)$

Where $n$ and $n$ are the length of wordList and the length of each string in wordList, respectively.