## 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 = {
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;
}
}
}

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 (!graph[word]) {
graph[word] = {};
}

}
}
}
}

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.