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];

        // 长度为一的字符串仅有 '*' 为有效的括号字符串
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '*') {
                dp[i][i] = true;
            }
        }

        // 长度为一的字符串仅有 '*' 为有效的括号字符串
        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;
            }
        }

        // 长度大于等于三的字符串，需要依赖内部字符串的判断结果
        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
38
39
class Solution {
    public boolean checkValidString(String s) {
        Stack<Integer> leftBracketIndexStack = new Stack<>();
        Stack<Integer> asteriskIndexStack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (c == '(') {
                leftBracketIndexStack.push(i);
            } else if (c == ')') {
                if (!leftBracketIndexStack.isEmpty()) {
                    leftBracketIndexStack.pop();
                } else if (!asteriskIndexStack.isEmpty()) {
                    asteriskIndexStack.pop();
                } else {
                    return false;
                }
            } else {
                // c == '*'
                asteriskIndexStack.push(i);
            }
        }

        // 剩余的左括号一定要匹配完，可以余出多个 '*' 充当空字符串
        while (!leftBracketIndexStack.isEmpty()) {
            if (asteriskIndexStack.isEmpty()) {
                return false;
            }
            int asteriskIndex = asteriskIndexStack.pop();
            int leftBracketIndex = leftBracketIndexStack.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; // 剩余的左括号数量的下界与上界
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                leftMin++;
                leftMax++;
            } else if (c == ')') {
                leftMin--;
                leftMax--;
            } else {
                // c is '*'
                leftMin--; // 充当右括号时
                leftMax++; // 充当左括号时
            }
            
            if (leftMax < 0) {
                // 左括号不够用了
                return false;
            }
            // leftMin 与 leftMax 的差值由 '*' 导致
            leftMin = Math.max(0, leftMin); // 左括号数量不能为负数，此时撤销此前 '*' 替换为右括号的动作，可以用 '(*)' 加深理解
        }

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

References

678. Valid Parenthesis String