scramble string

class String
  include Enumerable

  def each
    each_char { |char| yield char }
  end
end

def split_parts(string)
  parts = Array.new
  0.upto(string.length-2) { |mid|
    parts[mid] = [string[0..mid].sort, string[mid+1..string.length-1].sort]
  }
  return parts
end

# @param {String} s1
# @param {String} s2
# @return {Boolean}
def is_scramble(s1, s2)
  return false unless s1.length == s2.length
  return s1 == s2 if (s1.length == 1)
  front_parts = split_parts(s1)
  back_parts = split_parts(s2)
  (0.upto(s1.length-2)).each { |mid|
    if (front_parts[mid][0] == back_parts[mid][0] and front_parts[mid][1] == back_parts[mid][1])
      if (is_scramble(s1[0..mid], s2[0..mid]) and is_scramble(s1[mid+1..s1.length-1], s2[mid+1..s2.length-1]))
        return true
      end
    end
    mid2 = s1.length-2 - mid
    if (front_parts[mid2][0] == back_parts[mid][1] and front_parts[mid2][1] == back_parts[mid][0])
      if (is_scramble(s1[0..mid2], s2[mid+1..s2.length-1]) and is_scramble(s1[mid2+1..s1.length-1], s2[0..mid]))
        return true
      end
    end
  }
  return false
end

puts is_scramble("great", "rgeat")
puts is_scramble("great", "rgtae")
puts is_scramble("great", "taegr")
puts is_scramble("abcdd", "dbdac")

# puts split_parts("hello").inspect