678 Valid Parenthesis String

Search…
678. Valid Parenthesis String​
1. Question
Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules:
1.Any left parenthesis'('must have a corresponding right parenthesis')'.
2.Any right parenthesis')'must have a corresponding left parenthesis'('.
3.Left parenthesis'('must go before the corresponding right parenthesis')'.
4.'*'could be treated as a single right parenthesis')'or a single left parenthesis'('or an empty string.
5.An empty string is also valid.
Example 1:
1
Input: "()"
2
Output: True
Copied!
Example 2:
1
Input: "(*)"
2
Output: True
Copied!
Example 3:
1
Input: "(*))"
2
Output: True
Copied!
Note:
1.The string size will be in the range [1, 100].
2. Implementation
(1) Recursion
思路: 如果这题没有"*"，那么只要维护一个变量count，从左到右扫一遍，count在过程中不为负，且最后count等于0即可。但现在多了一个"*"，那我们就通过递归尝试3种可能性，即"*"表示为左括号，"*"表示为右括号，"*"为空。
1
class Solution {
2
    public boolean checkValidString(String s) {
3
        return check(s, 0, 0);
4
    }
5
​
6
    public boolean check(String s, int pos, int count) {
7
        if (pos == s.length()) {
8
            return count == 0;
9
        }
10
​
11
        if (count < 0) {
12
            return false;
13
        }
14
​
15
        if (s.charAt(pos) == '(') {
16
            return check(s, pos + 1, count + 1);
17
        }
18
        else if (s.charAt(pos) == ')') {
19
            return check(s, pos + 1, count - 1);
20
        }
21
        // check all possible cases when current character is "*"
22
        else {
23
            return check(s, pos + 1, count + 1) || check(s, pos + 1, count - 1) || check(s, pos + 1, count);
24
        }
25
    }
26
}
Copied!
(2) Two Pointers
思路: 用两个变量，low表示把"*"看做右括号时，左括号的个数(即左括号的lower bound), high表示把"*"看做左括号时，左括号的个数(即左括号的upper bound)。显然，当high小于0时，说明即使把"*"看做左括号, 也不能够抵消右括号，所以返回false。那么从左到右扫一遍输入string，遇到左括号时，low和high都加1，遇到右括号时，只有low大于0时才减1,这是为了保证low不小于0，high减1。遇到"*"时，根据high的定义high加1，low大于0才减1。最后查看low的个数即可。
1
class Solution {
2
    public boolean checkValidString(String s) {
3
        int low = 0, high = 0;
4
​
5
        for (char c : s.toCharArray()) {
6
            if (c == '(') {
7
                ++low;
8
                ++high;
9
            }
10
            else if (c == ')') {
11
                if (low > 0) {
12
                    --low;
13
                }
14
                --high;
15
            }
16
            else {
17
                if (low > 0) {
18
                    --low;
19
                }
20
                ++high;
21
            }
22
​
23
            if (high < 0) {
24
                return false;
25
            }
26
        }
27
        return low == 0;
28
    }
29
}
Copied!
3. Time & Space Complexity
Recursion: 时间复杂度O(3^n), n是输入字符串长度。最坏的情况是输入string全是"*", 那么每个"*"都有3种可能性，空间复杂度O(n)，主要是递归的开销，递归深度最多为n
Two Pointers: 时间复杂度O(n), 空间复杂度O(1)
Recursion
736 Parse Lisp Expression
Last modified 2yr ago
Copy link
Contents
678. Valid Parenthesis String
1. Question
2. Implementation
3. Time & Space Complexity
678. Valid Parenthesis String​

1. Question

2. Implementation

3. Time & Space Complexity

678. Valid Parenthesis String
