gistfile1.rb

dict = ["a",
"abdominal","a", "ace", "acre", "arc", "are", "area", "c", "car", "care", "ceca", "e", "ear", "era", "err", "r", "race", "racer", "rare", "re", "rear", "rec"
]


def jumble(source,dict) # =>O(2n^2d + 2nd + n + nlogn + 1) => O(n^2d)
    matches = [] # => O(1)
    source_array = source.split("")
    dict.each do |w| # => O(2n^2 + n + n) * O(d) => O(2n^2d + 2nd)
        w_hash = {}
        w.split("").each_with_index {|c,i| w_hash[i] =c } # => O(n)
        source_array.each do |value| # => O(2n+1) * O(n) => O(2n^2 + n)
            hash = w_hash.select{|k,v| v == value} # => O(n)
            first_key = hash.keys.first# =>O(n)
            if hash != {} # => O(1)
              w_hash.delete(first_key) # => O(1)
            end  
        end
        if w_hash == {} # => O(1)
          matches << w  # => O(1)
        end        
    end
  return matches
end

jumble("racecar", dict)