Skip to content

Instantly share code, notes, and snippets.

@SixArm
SixArm / ld.rb
Created August 12, 2011 23:57
Levenshtein Distance coding challenge: find all words in a set that are connected
#!/usr/bin/env ruby
#
# Two words are "directly connected" if one word can transform into the other by any of:
# * substitution of one character for another, e.g. "tan" => "ton"
# * insertion of one character, e.g. "tan" => "than"
# * deletion of one character, e.g. "tan" => "an"
#
# Two words are "connected" if applying the rules above repeatedly can directly connect words:
# * e.g. "tan" => "ton" => "tone" => "one" => "on"
# * e.g. "tan" => "an" => "in" => "pin" => "pink"