题目
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()" 输出：true
示例 2：
输入：s = "()[]{}" 输出：true
示例 3：
输入：s = "(]" 输出：false
示例 4：
输入：s = "([)]" 输出：false
示例 5：
输入：s = "{[]}" 输出：true
解题
方法一：堆栈（i）
总共三种情况,要输出False
- 左括号多
- 右括号多
- 左右括号没对应上
‘{ [ ( ) ] }’这种可以看出来，先进后出，所以此题用堆栈来解。
当c为左括号时，入栈。当c为右括号时，出栈，看看是否匹配，不匹配就为False。
python写法
class Solution: def isValid(self, s: str) -> bool: stack = [] hush2 = {")":"(","]":"[","}":"{"} for c in s: if c not in hush2: stack.append(c) else: if not stack: # 缺失左括号的情况 return False tmp = stack.pop() if hush2[c]!=tmp: return False #比如“{ ( )”这种情况，缺少右括号，还有左括号在堆栈中 if stack: return False return True
或者换种写法，本质是一样的
class Solution: def isValid(self, s: str) -> bool: hush = { '(':')', '[':']', '{':'}' } stack = [] for c in s: if c in hush: stack.append(c) else: if not stack: return False tmp = stack.pop() if hush[tmp]!=c: return False if stack: return False return True
c++写法
class Solution { public: bool isValid(string s) { unordered_map<char,char> map={ {'(',')'}, {'[',']'}, {'{','}'} }; stack<char> stack; for(char c:s){ if(map.find(c)!=map.end()){ stack.push(c); } else{ if(stack.empty()) return false; char tmp=stack.top();stack.pop(); if(map[tmp]!=c) return false; } } return stack.empty(); // if(!stack.empty()) return false; // return true; } };
java写法
class Solution { public boolean isValid(String s) { //匿名内部类 + 实例化代码块 Map<Character,Character> mp=new HashMap(){ { put('(',')'); put('[',']'); put('{','}'); } }; Stack<Character> st=new Stack<>(); for(int i=0;i<s.length();i++){ char c=s.charAt(i); if(mp.containsKey(c)){ st.push(c); }else{ if(st.isEmpty()) return false; Character tmp=st.peek(); if(mp.get(tmp)==c){ st.pop(); }else{ return false; } } } if(!st.isEmpty()) return false; return true; } }
