-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathValidParenthesisString.java
More file actions
41 lines (34 loc) · 1.81 KB
/
ValidParenthesisString.java
File metadata and controls
41 lines (34 loc) · 1.81 KB
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
// 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:
// 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.
// See: https://leetcode.com/problems/valid-parenthesis-string/
// See: https://leetcode.com/explore/featured/card/30-day-leetcoding-challenge/530/week-3/3301/
package leetcode.string;
public class ValidParenthesisString {
// Recursive solution.
// TODO: Add recursion with memorization, dynamic programming or greedy solution.
public boolean checkValidString(String s) {
return helper(s, 0, 0);
}
private boolean helper(String s, int i, int score) {
if (i == s.length() || score < 0)
return score == 0;
if (s.charAt(i) == '*')
return helper(s, i + 1, score - 1) || helper(s, i + 1, score + 1)
|| helper(s, i + 1, score);
else
return helper(s, i + 1, s.charAt(i) == '(' ? ++score : --score);
}
public static void main(String[] args) {
System.out.println(new ValidParenthesisString().checkValidString("()"));
System.out.println(new ValidParenthesisString().checkValidString("(*)"));
System.out.println(new ValidParenthesisString().checkValidString("(*))"));
System.out.println(new ValidParenthesisString().checkValidString("((((*"));
System.out.println(new ValidParenthesisString().checkValidString("(*(((*))"));
}
}