【LeetCode】20. Valid Parentheses 解題報告

20. Valid Parentheses / Easy

Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

An input string is valid if:
1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Example 1:

Input: s = “()”
Output: true

Example 2:

Input: s = “()[]{}”
Output: true

Example 3:

Input: s = “(]”
Output: false

Example 4:

Input: s = “([)]”
Output: false

Example 5:

Input: s = “{[]}”
Output: true

Comstraints

  • 1 <= s.length <= 104
  • s consists of parentheses only ‘()[]{}’.

Solution: Stack

思路

這題是很典型的堆疊題,利用 Stack 先進後出的特性就能很輕易地判斷括弧是否 valid。

一開始先檢查字串的長度是不是偶數,不是的話,括弧必定 invalid。
接著,如果是左括弧,就放入堆疊;右括弧則把堆疊最上方的元素拿來比較,如果是同一種括弧,就把元素 pop 出去,反之則回傳 false。

最後檢查堆疊是不是空的,若不是就回傳 false,例如 “((“ 這類只有左括弧的字串便會出現這種狀況。

至於判斷括弧對應的方式有很多種,可以用 if-else 或 switch 寫死,也可以用 map,我兩種都有寫,在這題對效能影響不大,記憶體用量則有輕微影響。

效能

Complexity

  • Time Complexity: O(N)
  • Space Complexity: O(N)

LeetCode Result

Code 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
bool isValid(string s) {
if(s.size() % 2 == 1) return false;
stack<char> sk;
for(char c : s) {
if(c == '(' || c == '[' || c == '{') {
sk.push(c);
} else {
if(sk.empty()) return false;
if(sk.top() == '(' && c != ')') return false;
if(sk.top() == '[' && c != ']') return false;
if(sk.top() == '{' && c != '}') return false;
sk.pop();
}
}
if(!sk.empty()) return false;
return true;
}
};

Code 2: With Map

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
bool isValid(string s) {
if(s.size() % 2 == 1) return false;
stack<char> sk;
map<char, char> m {
{'(', ')'},
{'[', ']'},
{'{', '}'}
};

for(char c : s) {
if(c == '(' || c == '{' || c == '[') {
sk.push(c);
} else {
if(sk.empty() || m[sk.top()] != c) {
return false;
} else {
sk.pop();
}
}
}
if(!sk.empty()) return false;
return true;
}
};