方針
文字列を左から右へ走査し、まだ対応する閉じ括弧がない開き括弧をスタックに積みます。各文字を処理する直前、スタックにはこれまでに見た開き括弧のうち、まだ対応付けられていないものだけが元の順序で残っています。そのため、閉じ括弧が現れたら、直前に現れた開き括弧と対応していなければなりません。スタックが空の場合、または括弧の種類が一致しない場合、文字列は無効です。走査後にスタックが空の場合に限り、文字列は有効です。スタックに開き括弧が残っていれば、対応する閉じ括弧がありません。
問題の制約により、文字列に含まれるのは ()[]{} のみです。各文字を一度処理するため、時間計算量は O(N) です。最悪の場合、すべての文字が開き括弧なので、追加の空間計算量は O(N) です。
Java
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
27
28
29
import java.util.ArrayDeque;
import java.util.Deque;
class Solution {
public boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(' || c == '{' || c == '[') {
stack.push(c);
continue;
}
if (stack.isEmpty()) {
return false;
}
char opener = stack.pop();
if ((c == ')' && opener != '(')
|| (c == '}' && opener != '{')
|| (c == ']' && opener != '[')) {
return false;
}
}
return stack.isEmpty();
}
}