0678. Valid Parenthesis String (Medium)
Question
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].
分析/解題
給定一個字串，當中僅含三種字元：’(’, ‘)’, ‘*’ (左括號，右括號及米字號)，試寫一個函式以檢查這個字串是否有效。
一個字串要符合以下的規則才算是有效的：
- 任一個左括號都要有一個對應的右括號
- 任一個右括號都要有一個對應的左括號
- 左括號必須出現在其對應的右括號之前
- 米字號(*)可以被視為單一個右括號、左括號、或空字串
- 空字串也是有效的
綜合上面的描述，我們可以知道像是：
‘)(’ -> 右括號還沒對應就出現在左括號前所以是False；
但像是‘(()()*)’ 就會是True，
仔細觀察可以發現，如果我們先不考慮米字號的部分，
從左到右，左括號出現的次數必然 >= 右括號出現的次數。
(因為要兩兩相對應，且右括號不能還沒對應到就出現在左括號之前)
所以，如果是沒有米字號的話，這題會相當簡單：
定義一個cnt(初始值為0)，由左至右，
每次碰到左括號則+1，右括號則-1 ，中間如果cnt變為負數 ，
則代表有右括號還沒對應到就出現了 ，則有效性是False ；
而遍歷整個字串到結尾時，
如果cnt變為0 的話則有效性是True (剛好所有括號兩兩對應)，
否則則為False (還有未對應到的括號)。
那麼，加上米字號的話該怎麼辦呢？
我們可以先將所有的米字號當成左括號來用 ，
由左至右檢查是否左括號足夠配對右括號完還有剩。
假設中途左括號不夠的話 ，肯定是False (因為加上米字號都不夠用)；
配對完剛好用完 -> ** True**(因為所有的米字號全拿來當左括號剛好OK)
配對完左括號還有剩 呢？
這時候我們應該從右至左， 換成將所有的米字號當成右括號來用，
換成檢查右括號足不足夠配對。
中途右括號不夠 -> False；
最後如果右括號數量足夠的話，則為True。
最後一段我們需要更仔細的考慮原因：
有沒有可能在由左至右留下來多出來的部分是左括號呢？
答案是否定的，因為如果是這樣的話，這些多出來的部分，
在反方向的時候會因為它們不是米字號，使得右括號的數量不夠用 ，
從而讓中途不足以配對 的狀況發生。
所以要嘛就是剛好完全配對 ，不然的話，就是剩下的全都是米字號 ，
這樣反向時才有辦法處理。
所以，當雙向都能夠順利滿足的時候，
只要將多出來的米字號視作空字串，就能使整個字串得以滿足有效性了！
依照上面的邏輯，我們可以進行 two pass 經過整個字串，
完成整個檢查工作，其空間複雜度為O(1)，時間複雜度為O(n)。
(n為字串的長度)
寫成程式碼如下。
Java
Java的部分，使用charAt()來取得特定index的字元，
並分別設定l跟r變數來計算。(要設成同一個cnt變數也行，自己歸零即可)
Python
Python的部分，這邊使用三元運算子處理。
此外，如果不想用index一個一個數的話，
用for c in s以及for c in reversed(s)也可以。
讀者可能會留意到註解裡有附註了lee215的one pass解法 ，
有興趣的可以再深入了解。具體的思路是記錄從左至右途中，
我們現在需要等待多少右括號來將一組括號完整；
cmax 是將所有碰到的*都當作是左括號 處理，
(也就是最大可能 會產生尚未配對的左括號數量)
而cmin 是中間能消去配對的狀況就消去 。
(也就是最少一定 要被配對完成的左括號數量)
按這個條件的話，cmax必然要一直>=0，
且cmin再結尾時要剛好是0才可以。
面試實際可能會遇到的問題
「時間/空間複雜度？」
(O(n)/O(1)，n為字串長度，空間不論是哪種方式都只需常數大小)
「如果不管空間複雜度，你能使用stack來解這題嗎？」
(可以做配對然後將成對的括號吐掉，
具體可以參考以下幾個discussion的解法。
Java: https://leetcode.com/problems/valid-parenthesis-string/discuss/107572/Java-using-2-stacks.-O(n)-space-and-time-complexity.
相似及延伸
Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)
從LeetCode學演算法，我們下次見囉，掰~
感謝大家對這系列文章的支持！這邊跟大家自我工商一下：
筆者開設的系列同名線上課程：
「從Leetcode學演算法｜基礎篇」已經上線啦！ 在這堂課中，你將學會利用十種演算法/資料結構來優化解題過程，
並實際完整練習20題 精選考古題，
進而逐漸提升到不需提示也可以突破白板題，取得工作門票！
Medium優惠(最後一波早鳥優惠了，不確定調回原價是什麼時候)： ** https://hiskio.com/courses/319?promo_code=VE9Q5VE**