Last Updated on 2022-03-13 by Clay
題目
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Example:
Input: s = "()[]{}"
Output: true
Input: s = "([)]"
Output: false
Input: s = "{[]}"
Output: true
題目會給輸入一個字串，該字串只會由以下符號組成：
- (
- )
- [
- ]
- {
- }
而我們要判斷這些括弧的組合是否『合法』，左方符號一定要對應右方符號，符號的中間可以放入合法符號。詳情請參考上方的範例。
解題思路
這題是使用 stack 解題的經典範例。我們只要碰到 (、{、[ 就將其放入 stack 中，如果遇到 )、}、] 則匹配 stack 的最頂部（stack 是後進先出的資料結構），如果是合法的匹配，則將其 stack 頂部的字符彈出。
如果 stack 為空，而又碰到了需要匹配 )、}、] 的情況，則意味著這是個不合法的字串，直接回傳 false。如果匹配到最後 stack 為空，回傳 true、反之則 false。
用文字有些難以說明，我們假設現在題目的輸入是 " { [ ( ) ] }" 這樣的字串。
| 步驟 | 陣列 | 解釋 |
| 1 | { | 只有一個字元，不需計算是否合法 |
| 2 | { [ | 放入 |
| 3 | { [ ( | 持續放入 |
| 4 | { [ ( ) | 合法，彈出 ( |
| 5 | { [ ] | 合法，彈出 [ |
| 6 | { } | 合法，彈出 { |
| 7 | 字串輸入完畢，陣列為空，返回 true |
C++ 程式碼
class Solution {
public:
bool isValid(string s) {
// Init
stack<char> st;
// Matching
for (char c: s) {
if (c == '(' || c == '{' || c == '[') {
st.push(c);
}
else if (st.empty()) {
return false;
}
else if (st.top() == '(' && c != ')') return false;
else if (st.top() == '{' && c != '}') return false;
else if (st.top() == '[' && c != ']') return false;
// Pop
else st.pop();
}
return (st.empty());
}
};Python 程式碼
class Solution:
def isValid(self, s: str) -> bool:
# Init
st = []
# Matching
for c in s:
if c in ['(', '{', '[']:
st.append(c)
elif len(st) == 0: return False
elif st[-1] == '(' and c != ')': return False
elif st[-1] == '{' and c != '}': return False
elif st[-1] == '[' and c != ']': return False
else: st.pop()
return len(st) == 0