aboutsummaryrefslogtreecommitdiff
path: root/other/valid_parentheses.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/valid_parentheses.cpp')
-rw-r--r--other/valid_parentheses.cpp43
1 files changed, 43 insertions, 0 deletions
diff --git a/other/valid_parentheses.cpp b/other/valid_parentheses.cpp
new file mode 100644
index 0000000..9bab082
--- /dev/null
+++ b/other/valid_parentheses.cpp
@@ -0,0 +1,43 @@
+// 20. Valid Parentheses
+#include "leetcode.h"
+
+/*
+ * given a string 's' containing just the characters '(, ), {, }, [, ]',
+ * determine if the input string is valid. a 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. every close bracket has a corresponding open
+ * bracket of the same type.
+ */
+
+class Solution {
+public:
+ bool isValid(string s) {
+ stack<char> stk;
+ for (int i = 0; i < s.size(); i++) {
+ char ch = s[i];
+ if (ch == '(' || ch == '{' || ch == '[')
+ stk.push(ch);
+ else {
+ if (!stk.empty()) {
+ char top = stk.top();
+ if ((ch == ')' && top == '(') || (ch == '}' && top == '{') ||
+ (ch == ']' && top == '['))
+ stk.pop();
+ else
+ return false;
+ } else
+ return false;
+ }
+ }
+ if (stk.empty())
+ return true;
+ return false;
+ }
+};
+
+int main() {
+ Solution obj;
+ printf("%d\n", obj.isValid("()")); // expect: 1
+ printf("%d\n", obj.isValid("()[]{}")); // expect: 1
+ printf("%d\n", obj.isValid("(]")); // expect: 0
+}