-
Notifications
You must be signed in to change notification settings - Fork 0
/
Solution.java
42 lines (40 loc) · 1.38 KB
/
Solution.java
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
package validparenthesisstring;
/**
* 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:
* <p>
* Any left parenthesis '(' must have a corresponding right parenthesis ')'.
* Any right parenthesis ')' must have a corresponding left parenthesis '('.
* Left parenthesis '(' must go before the corresponding right parenthesis ')'.
* '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.
* An empty string is also valid.
* Example 1:
* Input: "()"
* Output: True
* Example 2:
* Input: "(*)"
* Output: True
* Example 3:
* Input: "(*))"
* Output: True
* Note:
* The string size will be in the range [1, 100].
*/
class Solution {
/**
* Approach - Greedy
* <p>
* Runtime: 0 ms, faster than 100.00% of Java online submissions for Valid Parenthesis String.
* Memory Usage: 37.6 MB, less than 5.00% of Java online submissions for Valid Parenthesis String.
*/
// TODO: Other solutions(BF, DP)
boolean checkValidString(String s) {
int lo = 0, hi = 0;
for (char c : s.toCharArray()) {
lo += c == '(' ? 1 : -1;
hi += c != ')' ? 1 : -1;
if (hi < 0) break;
lo = Math.max(lo, 0);
}
return lo == 0;
}
}