def _is_interleave(s1, s2, s3)
  return s2 == s3 if (s1.empty?)
  return s1 == s3 if (s2.empty?)
  return false if ($dp1[s1] == s3)
  if (s1[0] == s3[0])
    return true if _is_interleave(s1[1..-1], s2, s3[1..-1])
  end
  if (s2[0] == s3[0])
    return true if _is_interleave(s1, s2[1..-1], s3[1..-1])
  end
  $dp1[s1] = s3
  return false
end

def is_interleave(s1, s2, s3)
  $dp1 = Hash.new
  return false unless s1.length + s2.length == s3.length
  return _is_interleave(s1, s2, s3)
end