Poison

678. Valid Parenthesis String

DP
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public boolean checkValidString(String s) {
int n = s.length();

// 定义 dp[i][j] 为字符串 s[i, j] 是否为有效的括号字符串
// dp[i][j] depends on dp[i + 1][j - 1]
// dp[i][j] depends on dp[i][k] & dp[k + 1][j]
boolean[][] dp = new boolean[n][n];

// when sub str length = 1
for (int i = 0; i < n; i++) {
if (s.charAt(i) == '*') {
dp[i][i] = true;
}
}

// when sub str length = 2
for (int i = 0; i < n - 1; i++) {
char a = s.charAt(i), b = s.charAt(i + 1);
if ((a == '(' || a == '*') && (b == ')' || b == '*')) {
dp[i][i + 1] = true;
}
}

// when sub str length >= 3
for (int i = n - 3; i >= 0; i--) {
char a = s.charAt(i);
if (a == ')') {
continue;
}

for (int j = i + 2; j < n; j++) {
char b = s.charAt(j);
if (b == '(') {
continue;
}

dp[i][j] |= dp[i + 1][j - 1];
for (int k = i; k < j && !dp[i][j]; k++) {
dp[i][j] = dp[i][k] && dp[k + 1][j];
}
}
}

return dp[0][n - 1];
}
}
Stack
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
30
31
32
33
34
35
36
37
class Solution {
public boolean checkValidString(String s) {
Stack<Integer> leftBracketStack = new Stack<>();
Stack<Integer> asteriskStack = new Stack<>();

for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
leftBracketStack.push(i);
} else if (c == ')') {
if (!leftBracketStack.isEmpty()) {
leftBracketStack.pop();
} else if (!asteriskStack.isEmpty()) {
asteriskStack.pop();
} else {
return false;
}
} else {
// c == '*'
asteriskStack.push(i);
}
}

while (!leftBracketStack.isEmpty()) {
if (asteriskStack.isEmpty()) {
return false;
}
int leftBracketIndex = leftBracketStack.pop();
int asteriskIndex = asteriskStack.pop();
if (asteriskIndex < leftBracketIndex) {
return false;
}
}

return true;
}
}
Greedy
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
class Solution {
public boolean checkValidString(String s) {
int leftMin = 0, leftMax = 0; // 剩余的左括号数量的上界与下界:[leftMin, leftMax]

for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
leftMin++;
leftMax++;
} else if (c == ')') {
// 此时可抵消一个左括号,但是左括号下界为 0 时不能抵消左括号,此时可以选择抵消 '*', 若 '*' 不足则直接返回 false
leftMin = Math.max(leftMin - 1, 0);
leftMax--;
if (leftMax < 0) {
return false;
}
} else {
// c == '*'
// 充当右括号时,若此时没有左括号了,如字符串 "*",则不能抵消左括号,所以需要保持 leftMin 为 0
leftMin = Math.max(leftMin - 1, 0);
// 充当左括号时
leftMax++;
}
}

return leftMin == 0; // 左括号是否能被匹配完
}
}
Reference

678. Valid Parenthesis String