Skip to content

Instantly share code, notes, and snippets.

@jemise111
Created June 18, 2014 13:34
Show Gist options
  • Star 2 You must be signed in to star a gist
  • Fork 2 You must be signed in to fork a gist
  • Save jemise111/90a9bac520c2db80f7e3 to your computer and use it in GitHub Desktop.
Save jemise111/90a9bac520c2db80f7e3 to your computer and use it in GitHub Desktop.
require 'Benchmark'
def balanced_delimiters?(text)
openers = []
matchers = {
')' => '(',
']' => '[',
'}' => '{'
}
text.chars.each do |char|
if matchers.values.include?(char)
openers.push(char)
else
if openers.last == matchers[char]
openers.pop
else
return false
end
end
end
openers.empty?
end
# Sample Test Cases
# ------------------
test_text = ['(){}', '([{}])', '({})', '([)]', '(', ')', '([})']
test_text.each do |test|
puts balanced_delimiters?(test)
end
# Test Time Complexity
# ---------------------
test_text_2 = '({{([])}})' * 1_000
test_text_3 = '({{([])}})' * 10_000
test_text_4 = '({{([])}})' * 100_000
puts Benchmark.measure { balanced_delimiters?(test_text_2) }
puts Benchmark.measure { balanced_delimiters?(test_text_3) }
puts Benchmark.measure { balanced_delimiters?(test_text_4) }
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment