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

有效字符串需滿足：

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;
}

總結

以上是生活随笔為你收集整理的leetcode-20 有效的括号匹配的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。