首页 > leetcode-20 有效的括号匹配

leetcode-20 有效的括号匹配

给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串

示例 1:

输入: “()”

输出: true

示例 2:

输入: “()[]{}”

输出: true

方法一：

遇到左括号，压栈

遇到右括号，弹栈

bool isValid(string s) { if(s.length() == 0) return true;stack<char> S;for (int i = 0;i < s.length(); ++i) { switch(s[i]) { case ')':{ if(!S.empty()) { if(S.top() == '('){ S.pop();} else { return false;}}else { return false;}break;}case ']':{ if(!S.empty()) { if(S.top() == '['){ S.pop();} else { return false;}}else { return false;}break;                    }case '}':{ if(!S.empty()) { if(S.top() == '{'){ S.pop();} else { return false;}}else { return false;}break;                    }case '(':{ S.push(s[i]);break;}case '[':{ S.push(s[i]);break;}case '{':{ S.push(s[i]);break;}}}if (S.size() != 0) { return false;}return true;
}

方法二：

同样的思路，优化代码逻辑，使用map建立括号之间的映射关系

bool isValid(string s) { map<char,int> m{ { '(',1},{ '[',2},{ '{',3},{ ')',4},{ ']',5},{ '}',6}};stack<char> st;bool res=true;for(char c:s){ int flag=m[c];if(flag>=1&&flag<=3) st.push(c);else if(!st.empty()&&m[st.top()]==flag-3) st.pop();else { res=false;break;}}if(!st.empty()) res=false;return res;
}

更多相关：

©2024 11GX.COM