The question
Given a source word, target word and an English dictionary, transform the source word to target by changing/adding/removing 1 character at a time, while all intermediate words being valid English words. Return the transformation chain which has the smallest number of intermediate words.
The solution
There are two parts to solving this problem. First we need to create a graph of the dictionary where each edge corresponds to a valid transformation of a word. We can represent this graph using a hash table (an object in JS). Then we do a breadth first search on this graph and that will give us the most efficient path.
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
var dictionary = {
ad: true,
at: true,
ate: true,
bat: true,
bed: true,
bet: true,
cat: true,
ed: true,
table: true
};
function createGraph(dict) {
var graph = {};
var letters = 'abcdefghijklmnopqrstuvwxyz';
var i;
var j;
// For all words
for (var word in dictionary) {
// For all characters in the word
for (i = 0; i < word.length; i++) {
// Remove character
var removeWord = word.substring(0, i) + word.substring(i + 1);
if (dictionary[removeWord]) {
if (!graph[word]) {
graph[word] = {};
}
graph[word][removeWord] = true;
}
// Change a character
for (j = 0; j < letters.length; j++) {
var changedWord = word.substring(0, i) + letters[j] +
word.substring(i + 1);
if (changedWord != word && dictionary[changedWord]) {
if (!graph[word]) {
graph[word] = {};
}
graph[word][changedWord] = true;
}
}
}
// Add a character
for (i = 0; i < word.length + 1; i++) {
for (j = 0; j < letters.length; j++) {
var addWord = word.substring(0, i) + letters[j] +
word.substring(i);
if (dictionary[addWord]) {
if (!graph[word]) {
graph[word] = {};
}
graph[word][addWord] = true;
}
}
}
}
return graph;
}
function transformWord(graph, start, goal) {
var paths = [[start]];
var extended = [];
while (paths.length) {
var currentPath = paths.shift();
var currentWord = currentPath[currentPath.length - 1];
if (currentWord === goal) {
return currentPath;
} else if (-1 !== extended.indexOf(currentWord)) {
continue;
}
extended.push(currentWord);
transforms = graph[currentWord];
for (var index in transforms) {
if (-1 === currentPath.indexOf(index)) {
var newPathStr = JSON.stringify(currentPath);
var newPath = JSON.parse(newPathStr);
newPath.push(index);
paths.push(newPath);
}
}
}
}
// This creates this graph:
// {
// ad: { ed: true, at: true },
// at: { ad: true, bat: true, cat: true, ate: true },
// ate: { at: true },
// bat: { at: true, cat: true, bet: true },
// bed: { ed: true, bet: true },
// bet: { bat: true, bed: true },
// cat: { at: true, bat: true },
// ed: { ad: true, bed: true }
// }
// Note that the word table is not there.
// This is because it doesn't have any connections
var graph = createGraph(dictionary);
function test() {
var path = transformWord(graph, 'ad', 'bed');
var expected = ['ad', 'ed', 'bed'];
if (JSON.stringify(path) === JSON.stringify(expected)) {
console.log('success');
}
}
test(); // Prints success
Since creating the graph can be done in a pre-processing step we can ignore that time. The complexity of a breadth first seach is O(n), so that is the complexity of this solution.
computer_science algorithms javascript programming