transform on word to other with intermediate words in dictionary, with min steps

algo_transformword.rb

# 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.


# - See more at: http://www.ardendertat.com/2011/10/17/programming-interview-questions-8-transform-word/
#this is pseudo code, untested
dict = Hash.new

build_dict(dict_arr)
  arr = []
  dict_arr.each do |word|
    # remove a char
    [0...dict.len-1].each do |i|
      remove = word[:i]+word[:i+1]
      if  dict_arr.include? remove
        arr<< remove
      end
    end
    #add a char
    [0...dict.len].each do |i|
      letters.each do |char|
        add = word[:i]+char+word[i:]
         if  dict_arr.include? add
            arr << add
          end
      end
    end
    #replace/transpose
    [0...dict.len-1].each do |i|
      letters.each do |char|
        transpose = word[:i] + char+ word[:i+1]
        if  dict_arr.include? transpose
            arr << transpose
        end
      end
    end
  dict[word] = arr #put arr in the dict  
  end
end

def findpath(startw,endw)
  path = Queue.new([startw])
  visited = Set.new
  # do a BFS 
  while path.isEmpty? do
    temp_arr = path.pop
    lastw = temp_arr[-1]
    if visited.contains? lastw
      next
    end
    visited.add(lastw)
    graph_nodes = dict[lastw]
    graph_nodes.each do |currw|
      unless temp_arr.contains? currw  #avoid loops
        temp_arr << currw
        path.add(temp_arr)
      end
    end
  end
end