有效的括号字符串(Valid Parenthesis String)

给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：

  1. 任何左括号 ( 必须有相应的右括号 )。
  2. 任何右括号 ) 必须有相应的左括号 ( 。
  3. 左括号 ( 必须在对应的右括号之前 )。
  4. * 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
  5. 一个空字符串也被视为有效字符串。

示例 1:

输入: "()"
输出: True

示例 2:

输入: "(*)"
输出: True

示例 3:

输入: "(*))"
输出: True

注意:

  • 字符串大小将在 [1，100] 范围内。
bool checkVaildSubstring(char * s, int i, int j){
    if(i > j) return true;
    if(s[i] == ')') {
        return false;
    }else if( s[i] == '*'){
        if (checkVaildSubstring(s, i+1,j)){
            return true;
        }
    }
    for (int k=i+1;k<= j;k++){
        if(s[k]==')' || s[k] == '*'){
            if(checkVaildSubstring(s,i+1,k-1) && checkVaildSubstring(s,k+1,j)){
                return true;
            }
        }
    }
    return false;
}

bool checkValidString(char * s){
    return checkVaildSubstring(s,0,strlen(s)-1);
}

这里会因为重复算相同的内容多次导致超时，因此我们可以用一个二维数组将算过的存起来，二维数组的i,j表示从索引i到索引j的这个子串是否计算过

bool checkVaildSubstring(char * s, int i, int j, int** cache){
    if(i > j) return true;
    if(cache[i][j] == 1) return true;
    if(cache[i][j] ==-1) return false;
    if(s[i] == ')') {
        cache[i][j] = -1;
        return false;
    }else if( s[i] == '*'){
        if (checkVaildSubstring(s, i+1,j,cache)){
            cache[i][j] = 1;
            return true;
        }
    }
    for (int k=i+1;k<= j;k++){
        if(s[k]==')' || s[k] == '*'){
            if(checkVaildSubstring(s,i+1,k-1,cache) && checkVaildSubstring(s,k+1,j,cache)){
                cache[i][j] = true;
                return true;
            }
        }
    }
    cache[i][j] = -1;
    return false;
}
bool checkValidString(char * s){
    int len = strlen(s);
    // 0表示没算过，1表示算过且为true，-1表示算过且为false
    int ** cache = malloc(sizeof(int*)*len);
    for (int i =0;i<len; i++){
        // calloc 和malloc的区别再与calloc会自动把内存初始化为0
        // malloc不初始化，分配到的空间中数据时随机数据
        cache[i] = calloc(len, sizeof(int));
    }
    bool isValid = checkVaildSubstring(s,0,strlen(s)-1,cache);
    for (int i = 0; i<len; i++){
        free(cache[i]);
    }
    free(cache);
    return isValid;
}

成对相消的思路

bool checkValidString(char * s){
    int minCount = 0; // 最少多少个 '('
    int maxCount = 0; // 最多多少个 '('
    for (int i =0;i<strlen(s);i++){
        if(s[i] == '('){
            minCount++;
            maxCount++;
        }else if(s[i] == ')'){
            minCount--;
            maxCount--;
        }else if(s[i] == '*'){
            minCount--;
            maxCount++;
        }
        if(maxCount < 0){
            return false;
        }
        if(minCount < 0){
            minCount = 0;
        }
    }
    // 其实看的就是最后这个范围中有没有0
    return minCount == 0;
}