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.

[ application_design  computer_science  algorithms  javascript  programming  ]
Sorting algorithms computer_science algorithms javascript programming
Raft for reaching consensus computer_science algorithms
The Rabin-Karp algorithm computer_science algorithms javascript programming
Load testing a Rails app with Vegeta application_design programming
House painting problem computer_science algorithms javascript programming