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.
Example 1:
Example 2:
Example 3:
Note:
- The string size will be in the range [1, 100].
Code
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
public class ValidParenthesisString { public 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; } public static void main(String[] args) { ValidParenthesisString vdObj=new ValidParenthesisString(); System.out.println(vdObj.checkValidString("()")); System.out.println(vdObj.checkValidString("(*)")); System.out.println(vdObj.checkValidString("(*))")); } } |
Output
We encourage you to write a comment if you have a better solution or having any doubt on the above topic.