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

有效字符串需滿足：

左括號必須用相同類型的右括號閉合。

左括號必須以正確的順序閉合。

每個右括號都有一個對應(yīng)的相同類型的左括號。

?

示例 1：

輸入：s = "()"

輸出：true

示例 2：

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

輸出：true

示例 3：

輸入：s = "(]"

輸出：false

?

提示：

1 <= s.length <= 104

s 僅由括號 '()[]{}' 組成

通過次數(shù)1,479,883提交次數(shù)3,357,490

來源：力扣（LeetCode）

鏈接：https://leetcode.cn/problems/valid-parentheses

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

注意：

剪枝技巧：當s為單數(shù)時必定返回false;

代碼：

class?Solution?{

public:

????bool?isValid(string?s)?{

????????stack<char>?box;

????????if(s.size()%2==1)return?false;

???????for(int?i=0;i<s.size();i++){

???????????if(s[i]=='(')box.push(')');

???????????else?if(s[i]=='[')box.push(']');

???????????else?if(s[i]=='{')box.push('}');

???????????else?if(box.empty()||s[i]!=box.top())return?false;

???????????else?box.pop();

???????}

???????return?box.empty();

????}

};

注意：

for循環(huán)中的第四個判斷要把box.empty()放在前面，不然有可能操作空棧然后出現(xiàn)異常