This repository has been archived by the owner on Jun 24, 2021. It is now read-only.
forked from hoanhan101/algo
-
Notifications
You must be signed in to change notification settings - Fork 0
/
valid_parentheses_test.go
97 lines (78 loc) · 1.67 KB
/
valid_parentheses_test.go
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
/*
Problem:
- Given a list of parentheses, determine if it is valid.
Example:
- Input: []string{"(", ")", "[", "]", "{", "}"}
Output: true
- Input: []string{"(", "[", ")", "]"}
Output: false
Approach:
- Use a stack push the opening parenthesis and pop the last inserted one when
we encounter a closing parenthesis and check if it is a valid match.
Cost:
- O(n) time, O(n) space.
*/
package leetcode
import (
"testing"
"github.com/hoanhan101/algo/common"
)
func TestIsValid(t *testing.T) {
tests := []struct {
in []string
expected bool
}{
{[]string{}, true},
}
for _, tt := range tests {
common.Equal(
t,
tt.expected,
isValid(tt.in),
)
}
}
func isValid(s []string) bool {
m := map[string]string{
"(": ")",
"{": "}",
"[": "]",
}
stack := newStack()
for _, p := range s {
// if p is an opening parenthesis, push it to the stack. otherwise, if
// is a closing parenthesis, pop the stack and check if they're matching
if _, ok := m[p]; ok {
stack.push(p)
} else if stack.size() == 0 || m[stack.pop()] != p {
return false
}
}
return stack.size() == 0
}
// stack represent a stack data structure.
type stack struct {
items []string
}
// newStack return a new Stack.
func newStack() *stack {
items := []string{}
return &stack{items: items}
}
// push a new item onto the stack.
func (s *stack) push(v string) {
s.items = append(s.items, v)
}
// pop remove and return the last item.
func (s *stack) pop() string {
// get the last item.
i := len(s.items) - 1
top := s.items[i]
// remove the last item.
s.items = s.items[:i]
return top
}
// size return the stack's size.
func (s *stack) size() int {
return len(s.items)
}