-
Notifications
You must be signed in to change notification settings - Fork 1
/
20-validParentheses.js
146 lines (120 loc) · 3.65 KB
/
20-validParentheses.js
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
//URL--
// https://leetcode.com/problems/valid-parentheses/
//INSTRUCTIONS--
/* Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
Constraints:
1 <= s.length <= 104
s consists of parentheses only '()[]{}'
*/
//SOLUTION--
/*
If the string is less than two long, return false
I am going to make an empty array called stack
Iterate through the string
If the character is any opening character, add it to the stack
If the character is a closing character, check to see if the correct character is at the top of the stack
If so, pop the top character off the stack
else return true
if stack length is 0, return true
else return false
*/
//original code
/**
* @param {string} s
* @return {boolean}
*/
// const isValid = function (s) {
// const stack = []
// function doBracesMatch(brace) {
// const pairs = {
// "}": "{",
// "]": "[",
// ")": "(",
// }
// const stackTop = stack.slice(-1)[0]
// if (stackTop === pairs[brace]) {
// return true
// } else {
// return false
// }
// }
// for (let i = 0; i < s.length; i++) {
// const character = s[i];
// if (character === "{" || character === "[" || character === "(") {
// stack.push(character)
// } else {
// if (doBracesMatch(character)) {
// stack.pop()
// }
// else {
// return false
// }
// }
// }
// return stack.length === 0
// };
//optimizations
/*
I did not need the check to see if the string is less than two long, so I removed it
//I removed the separate function to check if the top of the stack is a valid pair, and instead replaced with just checking to see if what is popped off the function is a valid pair
I added a check to see if the string has an odd length to get rid of unncessary calculations
*/
//optimized code
/**
* @param {string} s
* @return {boolean}
*/
const isValid = function (s) {
//if string length is odd, return false
if (s.length % 2 !== 0) {
return false
}
const stack = []
//pairs of valid brackets
const pairs = {
"}": "{",
"]": "[",
")": "(",
}
const openingBrackets = Object.values(pairs)
//iterate through the string
for (let i = 0; i < s.length; i++) {
const character = s[i];
//if the current character is an opening bracket, add it to the stack
if (openingBrackets.includes(character)) {
stack.push(character)
}
//else, pop the top value off the stack
else {
const stackTop = stack.pop()
//if the value isn't a valid opening bracket for the current closing bracket, return false
if (stackTop !== pairs[character]) {
return false
}
}
}
//if the stack is 0, return false, else return true
return stack.length === 0
};
//TESTCASES--
console.log(isValid("("), false);
console.log(isValid("(("), false);
console.log(isValid("((("), false);
console.log(isValid("()"), true);
console.log(isValid("(){}[]"), true);
console.log(isValid("(]"), false);
console.log(isValid("(())"), true);
console.log(isValid("(([][][]{}))"), true);
console.log(isValid("(([][][]{}))}"), false);