括号字符串的有效性和最长有效长度

一、题目

给定一个字符串 str，判断是不是整体有效的括号字符串。比如：

1 2	str="(()())" 返回 true str="()(" 返回 false

给定一个括号字符串 str，返回最长的有效括号子串

1 2	str="(()())" 返回 6 str="()(()()(" 返回 4

给你一个只包含三种字符的字符串，支持的字符类型分别是 ‘(‘、’)’ 和 ‘*’。请你检验这个字符串是否为有效字符串，如果是有效字符串返回 true 。

有效字符串符合如下规则：

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

1	s = "(*)" 返回 true

https://leetcode.cn/problems/valid-parenthesis-string/

等等这些判断括号有效性的题目很多

二、分析

针对第一个题目，比较简单，我们遍历整个字符串。

如果发现非 '(' 或 ')' 的字符，直接返回 false
定义一个变量 status，遇到 ( 字符，给他自增
遇到 ) 字符，给 status 减一，如果发现 status 为负数了，直接返回 false

class Solution {
public:
    bool is_valid(const std::string& str) {
        if (str.size() < 2) {
            return false;
        }
        int status = 0;
        for (int i = 0; i < str.size(); i++) {
            if (str[i] != '(' && str[i] != ')') {
                return false;
            }
            if (str[i] == ')' && --status < 0) {
                return false;
            }
            if (str[i] == '(') {
                status++;
            }
        }
        return status == 0;
    }
};

针对第二个题目，求有效的括号子串，使用动态规划。申请一个数组，和字符串的长度一致。dp[i] 值的含义为 str[0..i]中必须以字符 str[i] 结尾的最长的有效括号子串长度。

dp[0]=0，只含有一个字符肯定不是有效括号字符串，长度为 0
从左到右遍历 str[1...N-1] 的每个字符，假设遍历到 str[i]
如果 str[i]='(' ，有效括号字符串必须是以 ) 结尾，而不是以 ( 结尾。所以 dp[i]=0
如果 str[i]=')'，那么以 str[i] 结尾的最长有效括号子串可能存在。如果 "i - dp[i-1] - 1" 位置上的字符是 (，就能与当前位置的 str[i] 字符再配出一对有效括号。如果匹配到了，那么 dp[i] 的值起码是 dp[i-1]+2
还有一种情况是：()(()) ，比如遍历到最后一个字符 )，通过上面的过程找到的必须以最后字符结尾的最长有效括号子串是 (())，但是前面还有一段 ()。因此 str[i-dp[i-1]-1]和 str[i] 配成了一对，这时还应该把 dp[i-dp[i-1]-2]的值加到 dp[i] 中。
最终 dp[0 .. N-1] 中最大值就是最终的结果

class Solution2 {
public:
    int get_max_vaild_len(const std::string& str) {
        if (str.size() < 2) {
            return 0;
        }
        int res = 0;
        int pre = 0;
        std::vector<int> dp(str.size(), 0);
        for (int i = 1; i < str.size(); ++i) {
            if (str[i] == '(') {
                dp[i] = 0;
            }
            if (str[i] == ')') {
                pre = i - dp[i-1] - 1;
                if (pre >= 0 && str[pre] == '(') {
                    dp[i] = dp[i-1] + 2 + (pre-1 >= 0 ? dp[pre-1] : 0);
                }
            }
            res = std::max(res, dp[i]);
        }
        return res;
    }
};

对于第三题，我们使用贪心的做法。

从左到右遍历字符串，遍历过程中，未匹配的左括号数量可能会出现如下变化：

如果遇到左括号，则未匹配的左括号数量加 1
如果遇到右括号，则需要有一个左括号和右括号匹配，因此未匹配的左括号数量减 1
如果遇到星号，由于星号可以看成左括号、右括号或空字符串，因此未匹配的左括号数量可能加 1、减 1 或不变。

因此，基于上述结论，可以在遍历过程中维护未匹配的左括号数量可能的最小值和最大值，根据遍历到的字符更新最小值和最大值：

如果遇到左括号，则将最小值和最大值分别加 1
如果遇到右括号，则将最小值和最大值分别减 1
如果遇到星号，则将最小值减 1，将最大值加 1

任何情况下，未匹配的左括号数量必须非负，因此当最大值变成负数时，说明没有左括号可以和右括号匹配，返回 false

当最小值为 0 时，不应将最小值继续减少，以确保最小值非负。

遍历结束时，所有的左括号都应和右括号匹配，因此只有当最小值为 0 时，字符串 s 才是有效的括号字符串。

class Solution3 {
public:
    bool is_valid(const std::string& str) {
        if (str.empty()) {
            return true;
        }
        int min_value = 0;
        int max_value = 0;
        for (int i = 0; i < str.size(); ++i) {
            if (str[i] == '(') {
                min_value++;
                max_value++;
            } else if (str[i] == ')') {
                min_value = min_value != 0 ? --min_value : 0;
                max_value--;
            } else if (str[i] == '*') {
                min_value = min_value != 0 ? --min_value : 0;
                max_value++;
            }
            if (max_value < 0) {
                return false;
            }
        }
        return min_value == 0;
    }
};