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.

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`

`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_arrayend`
`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 Algorithm0.130797`
`Running Efficient Algorithm0.000167`
`----------------------`
`Running each algorithm 100 times`
`Running Naive Algorithm1.426623`
`Running Efficient Algorithm0.001131`
`----------------------`
`Running each algorithm 1000 times`
`Running Naive Algorithm13.533326`
`Running Efficient Algorithm0.011594`
`----------------------`
`Running each algorithm 10000 times`
`Running Naive Algorithm147.048088`
`Running Efficient Algorithm0.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.