首页 > 代码库 > LeetCode 20 Valid Parentheses
LeetCode 20 Valid Parentheses
问题：
Given a string containing just the characters ‘(‘, ‘)‘, ‘{‘, ‘}‘, ‘[‘ and ‘]‘, determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
提示：
Stack String
方法1：（效率低）
#include <stack>#include <string>class Solution {public: bool isValid(string s) { stack<char> mystack; for(int i=0; s[i]!=‘\0‘; i++){ char c=s[i]; switch(c){ case ‘(‘: case ‘[‘: case ‘{‘: mystack.push(c); break; case ‘)‘: if(mystack.empty() || mystack.top()!=‘(‘) return false; else mystack.pop(); break; case ‘]‘: if(mystack.empty() || mystack.top()!=‘[‘) return false; else mystack.pop(); break; case ‘}‘: if(mystack.empty() || mystack.top()!=‘{‘) return false; else mystack.pop(); break; } } return mystack.empty(); }};
方法2：（效率低）
#include <stack>#include <string>class Solution {public: bool isValid(string s) { stack<char> mystack; map<char,char> mymap; mymap.insert(pair<char,char>(‘(‘,‘)‘)); mymap.insert(pair<char,char>(‘[‘,‘]‘)); mymap.insert(pair<char,char>(‘{‘,‘}‘)); for(int i=0; s[i]!=‘\0‘; i++){ char c=s[i]; switch(c){ case ‘(‘: case ‘[‘: case ‘{‘: mystack.push(c); break; case ‘)‘: case ‘]‘: case ‘}‘: if(!mystack.empty()){ if(c!=mymap[mystack.top()]) return false; mystack.pop(); //pop()的返回值为void } else return false; break; } } return mystack.empty(); }};
该题别人用Java写的：https://segmentfault.com/a/1190000003481208
C++栈的申明：http://zhidao.baidu.com/link?url=DvEEXh4U47QLJnjmv6rAeMVk1V7A_5LCii42ctj8m2ehl1MepSy0w9BSWevmfuHwlstx0D60kvBNRvAoQgFtjK
C++栈操作：http://www.169it.com/article/2839007600903800247.html
C++ map操作：http://blog.sina.com.cn/s/blog_61533c9b0100fa7w.html
LeetCode 20 Valid Parentheses
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。