合法的括号字符串

C 解法, 执行用时: 3ms, 内存消耗: 404KB, 提交时间: 2022-07-25

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param s string字符串 
 * @return bool布尔型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
#include<stdbool.h>

char IsValid_positive(char* s ) 
{
    int Left_num = 0;
    int Right_num = 0;
    int Star_num = 0;
    
    
    if( *s == ')' ) return 0;
    
    while( *s )
    {
        switch( *s )
        {
            case '(':
                Left_num++;
                break;
            case '*':
                Star_num++;
                break;
            case ')':
                Right_num++;
                break;
        }
        s++;
        if( Right_num > Star_num+Left_num ) return 0;
    }
    return 1;
}


char IsValid_negative(char* s ) 
{
    int Left_num = 0;
    int Right_num = 0;
    int Star_num = 0;
    
    
    if( *s == '(' ) return 0;
    
    while( *s )
    {
        switch( *s )
        {
            case '(':
                Left_num++;
                break;
            case '*':
                Star_num++;
                break;
            case ')':
                Right_num++;
                break;
        }
        s--;
        if( Left_num > Star_num+Right_num ) return 0;
    }
    
    return 1;
}


bool isValidString(char* s ) 
{
    if( strlen(s)==0 ) return false;
    if( strlen(s) == 1 )
    {
        if( *s != '*' ) return false;
        else return true;
    }
    
    int len = strlen(s);
    
    char * res = ( char * )malloc( sizeof(char)*len );
    
    res = s+len-1;
    
    if( IsValid_positive(s)  && IsValid_negative(res) ) return true;
    else return false;

    
      

    
}

C++ 解法, 执行用时: 3ms, 内存消耗: 408KB, 提交时间: 2021-12-10

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    bool isValidString(string s) {
        // write code here
        int len=s.size();
        int cnt=0;
        for(int i=0;i<len;i++){
            if(s[i]==')'){
                cnt--;
                if(cnt<0)
                    return false;
            }
            else
                cnt++;
        }
        cnt=0;
        for(int i=len-1;i>=0;i--){
            if(s[i]=='('){
                cnt--;
                if(cnt<0)
                    return false;
            }
            else
                cnt++;
        }
        return true;
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 412KB, 提交时间: 2022-07-20

class Solution {
public:
    bool isValidString(string s) {
        stack<int> left;//保存左括号的下标
        stack<int> star;//保存星号的下标
        for(int i=0;i<s.size();i++){
            if(s[i]=='('){//左括号的下标进栈
                left.push(i);
            }else if(s[i]=='*'){//星号的下标进栈
                star.push(i);
            }else if(s[i]==')'){//右括号进行匹配
                if(!left.empty()){//先和左括号匹配
                    left.pop();
                }else if(!star.empty()){//如果左括号匹配失败则和星号匹配
                    star.pop();
                }else {//匹配不成功，字符串非法
                    return false;
                }
            }
        }
        //右括号全部匹配成功，判断左括号和星号是否合法
        while(!left.empty()&&!star.empty()){
            int lt=left.top();
            int st=star.top();
            left.pop();
            star.pop();
            if(st<lt){//星号如果不在左括号右边，非法
                return false;
            }
        }
        if(left.empty()){
            return true;
        }else return false;
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 412KB, 提交时间: 2022-05-13

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    bool isValidString(string s) {
        // write code here
        
        list<char> lt;
        for(char ch:s){
            if(ch=='(')
                lt.push_back(ch);
            else if(ch=='*')
                lt.push_back(ch);
            else{
                auto it=lt.rbegin();
                for(;it!=lt.rend()&&(*it)!='(';++it);
                
                if(it!=lt.rend()){
                    lt.erase((++it).base());
                }
                else if(lt.back()=='*'){
                    lt.pop_back();
                }
                else
                    return false;
            }
        }
        
        bool res=true;
        
        while(lt.empty()==false){
            auto it1=lt.begin();
            auto it2=lt.begin();
        
            for(;it1!=lt.end()&&(*it1)!='(';++it1);
        
            if(it1==lt.end()){
                res=true;
                break;
            }
        
            for(it2=it1;it2!=lt.end()&&(*it2)!='*';++it2);
            
            if(it2==lt.end()){
                res=false;
                break;
            }
            
            lt.erase(it1);
            lt.erase(it2);
        }
        
        return res;
    }
};

C 解法, 执行用时: 3ms, 内存消耗: 416KB, 提交时间: 2022-04-13

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param s string字符串 
 * @return bool布尔型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
bool isValidString(char* s ) {
    // write code here
    int mincount=0;
    int maxcount=0;
    int lens =strlen(s);
    for(int i=0;i<lens;i++){
        char c=s[i];
        if(c=='('){
            mincount++;
            maxcount++;
        }    
         else if(c==')'){
                if(mincount>0){
                    mincount--;
                }
                if(maxcount==0){
                    return false;
                }
                maxcount--;
            }
            //如果是*号，minCount减1，maxCount加1
            else{
                if(mincount>0){
                    mincount--;
                }
                maxcount++;
            }
        }
        //只要minCount为0，说明左括号能全部抵消掉，字符串合法
        return mincount==0;
}

详情