678. 有效的括號字符串

給定一個只包含三種字符的字符串：（ ，） 和 *，寫一個函數來檢驗這個字符串是否為有效字符串。有效字符串具有如下規則：

1. 任何左括號 ( 必須有相應的右括號 )。
2. 任何右括號 ) 必須有相應的左括號 ( 。
3. 左括號 ( 必須在對應的右括號之前 )。
4. • 可以被視為單個右括號 ) ，或單個左括號 ( ，或一個空字符串。
5. 一個空字符串也被視為有效字符串。

示例 1:輸入: "()"
輸出: True
示例 2:輸入: "(*)"
輸出: True
示例 3:輸入: "(*))"
輸出: True
注意:

字符串大小將在 [1，100] 范圍內。

解題思路

使用貪心算法，維護一個左括號的最大值和最小值

1. 當遇到（，左括號的數目加一，無論是最大值或者最小值
2. 當遇到），左括號的數目減去一，無論是最大值或者最小值。如果最大值小于0了，說明即使把所有的*換成（，也無法滿足）的需求
3. 當遇到*，我們可以將其當成（或者），當成），就需要把最小值減去1，因為消掉了一個（。當成（，就需要把最大值加上1

代碼

class Solution {public boolean checkValidString(String s) {int del=0,lMax=0,lMin=0,i=0,n=s.length();while(i<n){if(s.charAt(i)=='('){lMax++;lMin++;}else if(s.charAt(i)==')'){lMax--;lMin=Math.max(0,lMin-1);if(lMax<0)return false;}else {lMax++;lMin=Math.max(0,lMin-1);}i++;}return lMin==0;}
}