Given a start string, end string and a set of strings, find if there exists a path between the start string and end string via the set of strings.

find_path.rb

  # Given a start string, end string and a set of strings, find if there exists a path
  # between the start string and end string via the set of strings.
  # start: "cog" end: "bad"
  # set: ["bag", "cag", "cat", "fag", "con", "rat", "sat", "fog"]
  # one of the paths: "cog" -> "fog" -> "fag" -> "bag" -> "bad"
  def path_exists?(start_str, end_str, arr)
    return true if string_diff(start_str, end_str) == 1
    arr.each do |s|
      if string_diff(s, start_str) == 1
        arr.delete(s)
        return true if path_exists?(s, end_str, Array.new(arr))
      end
    end
    false
  end

  def string_diff(s1, s2)
    diff = 0
    (0...s1.size).each do |index|
      diff += 1 if s1[index] != s2[index]
    end
    diff
  end