blob: fc38c6965d6f9df1572d17d1d55b7cff7ef6d227 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
def assert_equal(x, y)
raise "Expected #{x.inspect}, Got #{y.inspect}" unless x == y
end
=begin
stack:
---
|[|
---
|{|
---
|(|
---
x
|(|{|[|)|]|
=end
class Solution
MATCHES = {
'(' => ')',
'[' => ']',
'{' => '}'
}.freeze
# space: O(n)
# time: O(n)
def self.run(input)
stack = []
for current in input.chars
if MATCHES[current]
stack.push(current)
elsif current == MATCHES[stack[-1]]
stack.pop
else
break
end
end
stack.empty?
end
end
assert_equal true, Solution.run("((()))")
assert_equal true, Solution.run("[()]{}")
assert_equal false, Solution.run("({[)]")
assert_equal false, Solution.run("()(){(())")
assert_equal true, Solution.run("")
assert_equal true, Solution.run("([{}])()")
puts "Yay!"
|
