diff options
Diffstat (limited to 'other/valid_parentheses.cpp')
-rw-r--r-- | other/valid_parentheses.cpp | 43 |
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 +} |