678. Valid bracket string

One 、 Title Description

Given a string containing only three characters ：（ ,） and *, Write a function to check whether the string is a valid string . Valid strings have the following rules ：

1. Any left parenthesis ( There must be a corresponding closing bracket ).
2. Any closing parenthesis ) There must be a corresponding left parenthesis ( .
3. Left parenthesis ( Must precede the corresponding closing bracket ).
4. • Can be treated as a single right parenthesis ) , Or a single left parenthesis ( , Or an empty string .
5. An empty string is also considered a valid string .

Example 1：

 Input : "()"
 Output : True

Example 2：

 Input : "(*)"
 Output : True

Example 3：

 Input : "(*))"
 Output : True

Two 、 Problem solving

Two traversal

Forward and backward traversal , Traverse from left to right , Determine the closing bracket , Traverse from right to left , Determine left parenthesis .

class Solution {
    
    public boolean checkValidString(String s) {
    
        // Two traversal , Forward and backward traversal , First determine whether the left bracket has a corresponding right bracket 
        int left = 0,cnt = 0;
        int length = s.length();
        char[] sch = s.toCharArray();
        for(char ch : sch){
    
            if(ch == '('){
    
                left++;
            }else if(ch == ')'){
    
                left--;
            }else{
    
                cnt++;
            }
            // Judge whether the current left bracket has a corresponding right bracket 
            if(left < 0){
    
                cnt--;
                left++;
            }
            if(cnt < 0){
    
                return false;
            }
        }
        // Traverse from right to left 
        int right = 0;
        cnt = 0;
        for(int i = length-1;i>=0;i--){
    
            char ch = sch[i];
            if(ch == ')'){
    
                right++;
            }else if(ch == '('){
    
                right--;
            }else{
    
                cnt++;
            }
            // Judge whether the current right bracket has a corresponding left bracket 
            if(right < 0){
    
                cnt--;
                right++;
            }
            if(cnt < 0){
    
                return false;
            }
        }
        return true;
    }
}

Time complexity ：O(n)
Spatial complexity ：O(1)

greedy

Traversing the string from left to right , During traversal , The number of unmatched left parentheses may change as follows ：

• If you encounter the left bracket , Then the number of unmatched left parentheses plus 1;

• If you encounter the right bracket , You need to have a left bracket and a right bracket match , Therefore, the number of unmatched left parentheses is reduced by 1;

• If you encounter an asterisk , Because the asterisk can be regarded as an open bracket 、 Right parenthesis or empty string , Therefore, the number of unmatched left parentheses may be increased by 1、 reduce 1 Or unchanged .

Based on the above conclusion , You can maintain the possible minimum and maximum values of the number of unmatched left parentheses during traversal , Update the minimum and maximum values according to the traversed characters ：

• If you encounter the left bracket , Then add the minimum and maximum values respectively 1;

• If you encounter the right bracket , Then the minimum and maximum values are reduced by 1;

• If you encounter an asterisk , Then reduce the minimum value by 1, Add... To the maximum 1.

In any case , The number of unmatched left parentheses must be non negative , So when the maximum becomes negative , No left parenthesis can match the right parenthesis , return false.

When the minimum value is 0 when , The minimum value should not be reduced , To ensure that the minimum value is non negative .

At the end of traversal , All left parentheses should match the right parenthesis , So only if the minimum value is 0 when , character string s Is a valid parenthesis string .

class Solution {
    
    public boolean checkValidString(String s) {
    
        // Greedy Algorithm 
        // Define two values , Record the maximum and minimum values of the matching left parentheses 
        int mincnt = 0,maxcnt = 0;
        int length = s.length();
        char[] sch = s.toCharArray();
        for(int i = 0;i<length;i++){
    
            char ch = sch[i];
            if(ch == '('){
    
                mincnt++;
                maxcnt++;
            }else if(ch == ')'){
    
                mincnt = Math.max(mincnt-1,0);
                maxcnt--;
                if(maxcnt < 0){
    
                    return false;
                }
            }else{
    
                mincnt = Math.max(mincnt - 1,0);
                maxcnt++;
            }
        }
        return mincnt == 0;
    }
}

Time complexity ：O(n)
Spatial complexity ：O(1)