Given a string s
containing only three types of characters: '('
, ')'
and '*'
, return true
if s
is valid.
The following rules define a valid string:
- 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""
.
Example 1:
Input: s = "()" Output: true
Example 2:
Input: s = "(*)" Output: true
Example 3:
Input: s = "(*))" Output: true
分析:
我们用lower and upper来表示“(”可能出现的最小次数和最大次数。但是如果lower小于0,那是一种invalid case,在upper大于0的这种情况下,我们可以把lower设为0进入下一轮。
1 class Solution { 2 public boolean checkValidString(String s) { 3 int upper = 0; 4 int lower = 0; 5 6 for (char letter : s.toCharArray()) { 7 switch (letter) { 8 case '(': lower++; upper++; break; 9 case ')': lower--; upper--; break; 10 case '*': lower--; upper++; break; 11 } 12 if (upper < 0) return false; 13 if (lower < 0) lower = 0; 14 } 15 return lower == 0; 16 } 17 }