【Leetcode】678. Valid Parenthesis String 有效的括号字元串

解法

跟沒有

*

的時候原理差不多，貪心，不斷統計待比對的左括号

(

的數量

left

，能比對的時候盡量比對

*

可以被分成三類：

• 未轉化的：它既可以轉化成

  (

  ，也可以轉化成

  )

• 轉化成

  )

  的：它可以通過跟一個遇不到左括号的

  )

  交換，重新變成未轉化的

  假設現在是這樣的場景

  (A*B)

  ，其中那個左括号是之前和

  *

  比對的那個左括号，而右括号是一個遇不到左括号的右括号。

  首先，

  A

  和

  B

  肯定是合法括号串。因為

  A

  裡的左括号必須要在

  A

  裡比對完了，才能輪到

  (A*B)

  裡這個左括号跟星号比對。同理，由于

  (A*B)

  裡的右括号是遇不到左括号的右括号，是以顯然

  B

  裡的左括号也已完全比對，是以

  B

  也是合法串。

  那麼，如果我們把

  (A*B)

  裡這個左括号跟目前這個遇不到左括号的右括号比對，那麼中間這個

  *

  就是未轉化的了。
• 轉化成

  (

  的：這部分的

  *

  相當于定死了，也不能轉回去了，也不可能被當成

  (

  用了

是以我們可以記錄前兩類

*

的數量：

unused

和

right

1. 每次遇到左括号

   (

   ，

   left

   加1
2. 每次遇到右括号

   )

   ：
   • 如果還有未比對的左括号，比對
   • 否則，如果有轉成

     )

     的

     *

     ，把它變成未轉化的
   • 否則，如果還有未轉化的

     *

     ，它把轉化成左括号

     (

   • 否則，這個右括号無法比對，傳回

     False

3. 每次遇到

   *

   ：
   • 如果有未比對的左括号

     (

     ，比對
   • 否則未轉化的

     *

     個數加一

class Solution:
    def checkValidString(self, s: str) -> bool:
        left = unused = right = 0
        for c in s:
            if c=='(':
                left += 1
            elif c==')':
                if left:
                    left -= 1
                elif right:
                    right -= 1
                    unused += 1
                elif unused:
                    unused -= 1
                else:
                    return False
            else:
                if left:
                    left -= 1
                    right += 1
                else:
                    unused += 1
        return left==0