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
Constraints:
1 <= s.length <= 100
s[i]
is'('
,')'
or'*'
.
A:
这个错了好多次。 哎~~~~~~悲伤~~~~~~~水平不够啊
看看这个,对不对?
class Solution { public: bool checkValidString(string s) { //from left to right, count of (+possible(, which is *, always >=0 //from left to right, count of )+possible(, which is *, always <=0 int cL = 0, cR = 0, cS = 0;//count of Left, Right, and Star for(const char ch : s){ if(ch=='('){ ++cL; }else if(ch==')'){ ++cR; }else{ // is * ++cS; } if(cR > cL + cS){ return false; } } return cL > cR+cS? false : true; } };
是错误的, 不能保证 *( 的情况
所以我们真正关心的,还是其 左右的balance情况,如果走一遍的话,核心是*(情况,第一个* 不能算)的。 因此需要 弄掉。
不需要stack, 只需要从左往右, 看 ‘)’ 会不会太多。
从右往左,看 '(' 有没有太多
class Solution { public: bool checkValidString(string s) { int n = s.length(); int cLeft = 0, cRight = 0, cStar = 0; // check forward, make sure ')' is not too many for(auto ch : s){ if(ch =='(') cLeft ++; else if(ch ==')') cRight++; else cStar++; if(cLeft + cStar < cRight) return false; } // check backward, make sure '(' is not too many cLeft = 0, cRight = 0, cStar = 0; for(int i = n-1;i>=0;i--){ if(s[i] =='(') cLeft ++; else if(s[i] ==')') cRight++; else cStar++; if(cLeft > cStar + cRight) return false; } return true; } };
稍微简化了一下。把3个变量用 map 表示
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | class Solution { public: bool checkValidString(string s) { unordered_map<char,int> M; // check forward, make sure ')' is not too many for(auto ch : s){ M[ch]++; if(M['('] + M['*'] < M[')']) return false; } M.clear(); // check backward, make sure '(' is not too many for(int i = s.length()-1;i>=0;i--){ M[s[i]]++; if(M['('] > M['*'] + M[')']) return false; } return true; } }; |
然而,官方答案用了DP 和greedy 2中方法。
Approach #3: Greedy [Accepted]
Intuition
When checking whether the string is valid, we only cared about the "balance
": the number of extra, open left brackets as we parsed through the string. For example, when checking whether '(()())' is valid, we had a balance of 1, 2, 1, 2, 1, 0
as we parse through the string: '('
has 1 left bracket, '(('
has 2, '(()'
has 1, and so on. This means that after parsing the first i
symbols, (which may include asterisks,) we only need to keep track of what the balance
could be.
For example, if we have string '(***)'
, then as we parse each symbol, the set of possible values for the balance
is [1]
for '('
; [0, 1, 2]
for '(*'
; [0, 1, 2, 3]
for '(**'
; [0, 1, 2, 3, 4]
for '(***'
, and [0, 1, 2, 3]
for '(***)'
.
Furthermore, we can prove these states always form a contiguous interval. Thus, we only need to know the left and right bounds of this interval. That is, we would keep those intermediate states described above as [lo, hi] = [1, 1], [0, 2], [0, 3], [0, 4], [0, 3]
.
Algorithm
Let lo, hi
respectively be the smallest and largest possible number of open left brackets after processing the current character in the string.
If we encounter a left bracket (c == '('
), then lo++
, otherwise we could write a right bracket, so lo--
. If we encounter what can be a left bracket (c != ')'
), then hi++
, otherwise we must write a right bracket, so hi--
. If hi < 0
, then the current prefix can't be made valid no matter what our choices are. Also, we can never have less than 0
open left brackets. At the end, we should check that we can have exactly 0 open left brackets.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | class Solution { public: bool checkValidString(string s) { // balance = [lo, hi] as the number of extra '(' than ')' int lo = 0,hi = 0; for(auto ch : s){ lo += ch=='(' ? 1:-1; hi += ch==')' ? -1:1; if(hi<0) return false; lo = max(lo,0); } return lo==0; } }; |
Complexity Analysis
Time Complexity: , where is the length of the string. We iterate through the string once.
Space Complexity: , the space used by our
lo
andhi
pointers. However, creating a new character array will take space.
No comments:
Post a Comment