05 August 2008
判断一个字符串是否是合法的括号组合，其中星号可以代表左括号或右括号
two stacks
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public boolean checkValidString(String s) {
Stack<Integer> leftID = new Stack<>();
Stack<Integer> starID = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (ch == '(')
leftID.push(i);
else if (ch == '*')
starID.push(i);
else {
if (leftID.isEmpty() && starID.isEmpty()) return false;
if (!leftID.isEmpty())
leftID.pop();
else
starID.pop();
}
}
while (!leftID.isEmpty() && !starID.isEmpty()) {
if (leftID.pop() > starID.pop())
return false;
}
return leftID.isEmpty();
}
Counter
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public boolean checkValidString(String s) {
int low = 0;
int high = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
low++;
high++;
} else if (s.charAt(i) == ')') {
if (low > 0) {
low--;
}
high--;
} else {
if (low > 0) {
low--;
}
high++;
}
if (high < 0) {
return false;
}
}
return low == 0;
}