題目

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

有效字符串需滿足：

1. 左括號必須用相同類型的右括號閉合。
2. 左括號必須以正確的順序閉合。
3. 每個右括號都有一個對應(yīng)的相同類型的左括號。

示例 1：

輸入：s = "()"
輸出：true

示例?2：

輸入：s = "()[]{}"
輸出：true

示例?3：

輸入：s = "(]"
輸出：false

思路

典型的棧問題，數(shù)據(jù)結(jié)構(gòu)書中都有用棧來作括號匹配的問題。

①字符串長度為奇數(shù)，直接返回false

②“( ] )”，當(dāng)有這樣的右括號時，也讓他入棧，最后判斷棧非空，則返回 false;

③“( ) { } } {”，

④“{ [ ] }”，

代碼

class Solution {
public:bool isValid(string s) {int len = s.length();bool flag;if (len % 2 != 0)flag = false;stack<char> st;int i;    for (i = 0; i < len; i++) {// 遇到左括號，入棧if (s[i] == 40 || s[i] == 91 || s[i] == 123) {  st.push(s[i]);}// 遇到右括號，取棧頂元素，看是否匹配。匹配則出棧，不匹配則入棧char a;if (s[i] == 41 || s[i] == 93 || s[i] == 125) {  // 遇到右括號時，棧中無元素，則直接返回falseif (st.empty()) {flag = false;break;}if (!st.empty()) {a = st.top();}if ((a == 40 && s[i] == 41) || (a == 91 && s[i] == 93) || (a == 123 && s[i] == 125)) {st.pop();   // 匹配則出棧}else{st.push(s[i]);  // 不匹配則入棧}}}if (i != len) {return flag;}if (i == len && st.empty())flag = true;return flag;}
};

答案思路：

建立map，鍵為右括號，值為左括號。

unordered_map<char, char> pairs = {{')', '('},{']', '['},{'}', '{'}
};