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. 1.
    Any left parenthesis'('must have a corresponding right parenthesis')'.
  2. 2.
    Any right parenthesis')'must have a corresponding left parenthesis'('.
  3. 3.
    Left parenthesis'('must go before the corresponding right parenthesis')'.
  4. 4.
    '*'could be treated as a single right parenthesis')'or a single left parenthesis'('or an empty string.
  5. 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. 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)