Word Ladder II

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        d = defaultdict(list)
        for word in wordList:
            for i in range(len(word)):
                d[word[:i]+"*"+word[i+1:]].append(word)

        if endWord not in wordList:
            return []

        visited1 = defaultdict(list)
        q1 = deque([beginWord])
        visited1[beginWord] = []

        visited2 = defaultdict(list)
        q2 = deque([endWord])
        visited2[endWord] = []

        ans = []
        def dfs(v, visited, path, paths):
            path.append(v)
            if not visited[v]:
                if visited is visited1:
                    paths.append(path[::-1])
                else:
                    paths.append(path[:])
            for u in visited[v]:
                dfs(u, visited, path, paths)
            path.pop()

        def bfs(q, visited1, visited2, frombegin):
            level_visited = defaultdict(list)
            for _ in range(len(q)):
                u = q.popleft()

                for i in range(len(u)):
                    for v in d[u[:i]+"*"+u[i+1:]]:
                        if v in visited2:
                            paths1 = []
                            paths2 = []
                            dfs(u, visited1, [], paths1)
                            dfs(v, visited2, [], paths2)
                            if not frombegin:
                                paths1, paths2 = paths2, paths1
                            for a in paths1:
                                for b in paths2:
                                    ans.append(a+b)
                        elif v not in visited1:
                            if v not in level_visited:
                                q.append(v)
                            level_visited[v].append(u)
            visited1.update(level_visited)

        while q1 and q2 and not ans:
            if len(q1) <= len(q2):
                bfs(q1, visited1, visited2, True)
            else:
                bfs(q2, visited2, visited1, False)

        return ans

Identifying Problem Isomorphism

“Word Ladder II” has an approximate isomorph: “Word Ladder”.

In “Word Ladder”, you are given two words (beginWord and endWord), and a dictionary’s word list. You need to find the length of the shortest transformation sequence from beginWord to endWord. You can change only one character at a time, and each transformed word must exist in the word list.

Similarly, in “Word Ladder II”, you are given the same inputs and can perform the same transformations, but your task is to find all shortest transformation sequences, not just the length of one sequence.

Both problems require you to explore transformation paths in a graph of words. In each case, nodes represent words, and an edge exists between two nodes if their corresponding words differ by one character. You’re tasked with finding a path or paths from one particular node to another. The shortest path algorithms like BFS can be used to solve these problems.

“Word Ladder II” is more complex as it asks for all shortest paths rather than a single shortest path as in “Word Ladder”.

“126. Word Ladder II” is a more advanced breadth-first search (BFS) problem that involves constructing the actual paths and not just finding the shortest path. It also involves elements of string manipulation and data structure use, especially with queues and hash maps.

10 Prerequisite LeetCode Problems

Here are 10 problems to build up the skills needed for this problem:

  1. “127. Word Ladder”:

    • This is a simpler version of “Word Ladder II” where you only need to find the length of the shortest transformation sequence.

  2. “200. Number of Islands”:

    • This is a good practice problem for understanding BFS in the context of a grid, which is similar to a graph.

  3. “207. Course Schedule”:

    • A classic problem that uses BFS to solve a graph problem about course prerequisites.

  4. “102. Binary Tree Level Order Traversal”:

    • This problem will provide you with practice using BFS in a tree context.

  5. “279. Perfect Squares”:

    • This problem also involves finding the shortest path in a graph using BFS.

  6. “49. Group Anagrams”:

    • This problem requires string manipulation and hash map use, similar to “Word Ladder II”.

  7. “347. Top K Frequent Elements”:

    • A great problem for practice using priority queues and hash maps.

  8. “139. Word Break”:

    • This problem combines elements of string manipulation and dynamic programming.

  9. “994. Rotting Oranges”:

    • Another BFS problem, this time applied to a grid. The problem involves tracking states and time, which is a helpful practice for “Word Ladder II”.

  10. “752. Open the Lock”:

  • This problem requires a breadth-first search and is a good analogy for the “Word Ladder II” problem, with a lock mechanism instead of words.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

	class Solution:
		def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
			d = defaultdict(list)
			for word in wordList:
				for i in range(len(word)):
					d[word[:i]+"*"+word[i+1:]].append(word)

			if endWord not in wordList:
				return []

			visited1 = defaultdict(list)
			q1 = deque([beginWord])
			visited1[beginWord] = []

			visited2 = defaultdict(list)
			q2 = deque([endWord])
			visited2[endWord] = []

			ans = []
			def dfs(v, visited, path, paths):
				path.append(v)
				if not visited[v]:
					if visited is visited1:
						paths.append(path[::-1])
					else:
						paths.append(path[:])
				for u in visited[v]:
					dfs(u, visited, path, paths)
				path.pop()

			def bfs(q, visited1, visited2, frombegin):
				level_visited = defaultdict(list)
				for _ in range(len(q)):
					u = q.popleft()

					for i in range(len(u)):
						for v in d[u[:i]+"*"+u[i+1:]]:
							if v in visited2:
								paths1 = []
								paths2 = []
								dfs(u, visited1, [], paths1)
								dfs(v, visited2, [], paths2)
								if not frombegin:
									paths1, paths2 = paths2, paths1
								for a in paths1:
									for b in paths2:
										ans.append(a+b)
							elif v not in visited1:
								if v not in level_visited:
									q.append(v)
								level_visited[v].append(u)
				visited1.update(level_visited)

			while q1 and q2 and not ans:
				if len(q1) <= len(q2):
					bfs(q1, visited1, visited2, True)
				else:
					bfs(q2, visited2, visited1, False)

			return ans

Problem Classification

This problem is about finding the shortest sequence of words from a start word to an end word where each word in the sequence only differs by one letter from its neighbors. This problem is about finding connections between words, so it’s a Word Connection Problem.

Language Agnostic Coding Drills

This problem is a variation of the classic problem of finding the shortest path in a graph. Here, each word in the wordList represents a node in the graph, and there is an edge between two words if they differ by a single character.

Here’s how to break down the code into drills:

1. Understanding Graphs

A graph is a mathematical structure that is comprised of a set of objects and a set of links that connect pairs of objects. It can be visualized as points (vertices or nodes) connected by lines (edges).

Drill: Create a simple graph data structure and implement methods to add nodes and edges. Then write a function to print all the edges in the graph.

2. Breadth-First Search (BFS) in Graphs

BFS is a graph traversal algorithm that explores nodes in a graph in breadthward motion. It uses a queue data structure to keep track of nodes to explore next.

Drill: Implement BFS on the graph you created. The function should take a starting node and print the nodes in the order they are visited.

3. Depth-First Search (DFS) in Graphs

DFS is another graph traversal algorithm. It explores as far as possible along each branch before backtracking.

Drill: Implement DFS on the graph you created. The function should take a starting node and print the nodes in the order they are visited.

4. Bidirectional BFS

This is a variant of BFS where the search begins from both the source vertex and the destination vertex. The search from two vertices meets at some point forming the BFS tree. This approach reduces the search space significantly.

Drill: Implement bidirectional BFS on your graph. The function should take a starting node and a target node and return the shortest path between them.

5. Default Dictionary Usage

A defaultdict is a dictionary-like object which provides all methods provided by a dictionary but takes a first argument as a default data type for the dictionary.

Drill: Create a defaultdict of lists. Add elements to the lists and print the defaultdict.

6. Problem-Specific Drill - Transforming Words

This problem involves transforming one word to another by changing a single character at a time. All intermediate words must exist in the wordList.

Drill: Given two words and a wordList, write a function that checks if the target word can be reached by changing a single character at a time. Use any graph traversal technique.

Once you understand these concepts and can implement the drills, you should be better equipped to understand and solve the findLadders problem.

Targeted Drills in Python

1. Understanding Graphs

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Graph:
    def __init__(self):
        self.graph = dict()

    def add_node(self, node):
        if node not in self.graph:
            self.graph[node] = []

    def add_edge(self, node1, node2):
        self.add_node(node1)
        self.add_node(node2)
        self.graph[node1].append(node2)
        self.graph[node2].append(node1)  # for undirected graph

g = Graph()
g.add_edge("apple", "mango")
g.add_edge("mango", "banana")
print(g.graph)

2. Breadth-First Search (BFS) in Graphs

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def BFS(graph, start):
    visited = set()
    queue = [start]

    while queue:
        vertex = queue.pop(0)
        print(vertex, end=" ")

        for neighbour in graph[vertex]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)

BFS(g.graph, "apple")

3. Depth-First Search (DFS) in Graphs

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def DFS(graph, start, visited=None):
    if visited is None:
        visited = set()

    visited.add(start)
    print(start, end=" ")

    for neighbour in graph[start]:
        if neighbour not in visited:
            DFS(graph, neighbour, visited)

DFS(g.graph, "apple")

4. Bidirectional BFS

1

# Bidirectional BFS is more complex to implement and is not covered here

5. Default Dictionary Usage

1
2
3
4
5
6

from collections import defaultdict

d = defaultdict(list)
d["fruits"].append("apple")
d["fruits"].append("banana")
print(d)

6. Problem-Specific Drill - Transforming Words

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

def transform_word(beginWord, endWord, wordList):
    wordSet = set(wordList)
    if endWord not in wordSet:
        return False
    queue = [(beginWord, 1)]
    while queue:
        word, length = queue.pop(0)
        if word == endWord:
            return length
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                next_word = word[:i] + c + word[i+1:]
                if next_word in wordSet:
                    wordSet.remove(next_word)
                    queue.append((next_word, length + 1))
    return 0

print(transform_word("hit", "cog", ["hot","dot","dog","lot","log","cog"]))

This transform_word function returns the shortest transformation sequence’s length from beginWord to endWord. If there is no such sequence, returns 0. It is a single directional BFS starting from beginWord.