20. 有效的括號(hào)
描述
- 給定一個(gè)只包括 '('，')'嗓违，'{'九巡，'}'，'['靠瞎，']' 的字符串，判斷字符串是否有效求妹。
- 有效字符串需滿足：
- 左括號(hào)必須用相同類型的右括號(hào)閉合乏盐。
- 左括號(hào)必須以正確的順序閉合。
- 注意空字符串可被認(rèn)為是有效字符串制恍。
示例
示例 1:
輸入: "()"
輸出: true
示例 2:
輸入: "()[]{}"
輸出: true
示例 3:
輸入: "(]"
輸出: false
示例 4:
輸入: "([)]"
輸出: false
示例 5:
輸入: "{[]}"
輸出: true
思路
- 基本的括號(hào)匹配算法父能，利用棧實(shí)現(xiàn)，左括號(hào)入棧净神、右括號(hào)與棧頂元素匹配何吝。
- 小技巧溉委，可以預(yù)先存放1個(gè)元素到棧內(nèi)，如'#'爱榕，后續(xù)就不用判空了瓣喊。
class Solution {
public:
bool isValid(string s) {
stack<char> ms;
for (char ch : s) {
if (ch == '(' || ch == '{' || ch == '[')
ms.push(ch);
else if (ch == ')') {
if (ms.empty() || ms.top() != '(') return false;
ms.pop();
} else if (ch == '}') {
if (ms.empty() || ms.top() != '{') return false;
ms.pop();
} else if (ch == ']') {
if (ms.empty() || ms.top() != '[') return false;
ms.pop();
}
}
return ms.empty();
}
};
