A Word Ladder Algorithm

A word ladder is a series of words created by changing one letter at a time. Here’s one example:

ball → tall → tale → take → lake → like

Problem

Given the four-letter word “lots”, what are all the words that could be adjacent to “lots” in a word ladder? You have access to this four-letter dictionary.

Example: if given the word “blue’, the algorithm should return: “clue, flue, glue, slue, blae, blub, blur”

Naive Solution

One straightforward approach would be to iterate over each letter in the four-character string, replacing the given letter by each letter in the alphabet. Then compare each string against the entire dictionary to see if we have a match. If so, add our string to the results array. Then we continue with our loops.

def word_ladder(word, dict)
  result = []
  word.chars.each_with_index do |letter, index|
    ('a'..'z').each do |changed_letter|
      duped_word = word.dup
duped_word[index] = changed_letter
      if dict.include?(duped_word) && duped_word != word
result << duped_word
end
    end
end
  result
end
dict = File.readlines('words.txt').each do |line|
line.strip!
end
word_ladder("lots", dict)

This approach has a linear time complexity, or O(n).

The Ideal Solution

A much more elaborate yet efficient approach when fully set up would involve the following:

  1. Produce an adjacency list of a graph with each word as a vertex and each adjacent word (a word off by only one letter) connected by an edge to the vertex.
  2. Read all the edges for your given vertex (word) by finding your word in your word array, then reading off all the edge values in the linked list

In Ruby, completing #1 by building the adjacency list could look something like this:

Word = Struct.new(:word, :successor)
class Adj_List
  attr_reader :dict_array
  def initialize(dict)
@dict = dict
@dict_array = []
end
# adds adjacent words to all words that are in the dictionary
   def add_edges
@dict.each do |word|
linked_list = build_linked_list(word)
add_edge(linked_list)
end
@dict_array
end
   private
    def build_linked_list(word)
linked_list = Word.new(word, nil)
word.chars.each_with_index do |letter, index|
(‘a’..’z’).each do |changed_letter|
duped_word = word.dup
duped_word[index] = changed_letter
if @dict.include?(duped_word) && duped_word != word
new_word = Word.new(duped_word, nil)
last_item = last_item_in_linked_list(linked_list)
last_item[:successor] = new_word
end
end
end
return linked_list
end
    def last_item_in_linked_list(linked_list)
until linked_list[:successor].nil?
linked_list = linked_list[:successor]
end
linked_list
end
    def add_edge(linked_list)
@dict_array << linked_list
end
end
dict = File.readlines('words.txt').each do |line|
line.strip!
end
adj_list =  Adj_List.new(dict)
adj_list.add_edges

Searching through the adjacency list for adjacent words becomes the following:

class Adj_List
# returns all adjacent words of a word
def find_adjacent_words(target_word)
index = binary_search(@dict_array, target_word)
word_array = return_near_words(@dict_array[index])
word_array.shift
word_array
end
private
def binary_search(array, word, from = 0, to = nil)
  if to == nil
to = array.count - 1
end
  mid = (from + to) / 2
  if word < array[mid].word
return binary_search(array, word, from, mid - 1)
elsif word > array[mid].word
return binary_search(array, word, mid + 1, to)
else
return mid
end
end
def return_near_words(word)
output_array = []
until word.nil?
output_array << word[:word]
word = word[:successor]
end
return output_array
end
end
adj_list.find_adjacent_words('lots')

Using the adjacency list approach I’ve outlined above, constructing the adjacency list is admittedly a fairly time intensive procedure (about a minute on my machine since the time complexity is O(n2). We could mitigate this by writing the adjacency list to a file for future reference).

However, once the adjacency list has been built, it’s extremely efficient to search for adjacent words. Time complexity is O(d), where d is the number of edges for a given vertex (In the above Ruby implementation, we don’t quite achieve O(d), since we must first binary search through the array to locate the word we want to find neighbors for).

Benchmarks

Running the naive and efficient algorithm yields the following benchmarks (tests were run after generating the adjacency list). As you can see, the naive algorithm’s time complexity is linear, while the efficient algorithm is ~ O(d)

Running each algorithm 10 times
----------------------
Running Naive Algorithm
0.130797
Running Efficient Algorithm
0.000167
----------------------
Running each algorithm 100 times
Running Naive Algorithm
1.426623
Running Efficient Algorithm
0.001131
----------------------
Running each algorithm 1000 times
Running Naive Algorithm
13.533326
Running Efficient Algorithm
0.011594
----------------------
Running each algorithm 10000 times
Running Naive Algorithm
147.048088
Running Efficient Algorithm
0.101792
----------------------
Like what you read? Give Luke Schleicher a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.