Description

给定一个长度为\(n\)的字符串\(s\)。每个字符只可能是:()或者*。其中*可以表示为()或者是空字符。问字符串\(s\)是否满足括号匹配。

Constraints

\(1 \le n \le 100\)

Solution

简单的区间DP,基本操作就不解释了。

这里使用了int[][]而不是bool[][]作为\(dp\)的类型,可以通过记录\(-1\)避免设立一个单独的\(vis\)表。

Code

class Solution {
public:
    bool checkValidString(string s) {
        int dp[103][103] {};
        memset(dp, -1, sizeof dp);
        auto valid = [&](int i, int j) {
            return  (s[i] == '(' && ( s[j] == ')' || s[j] == '*' ))
                ||  (s[j] == ')' && ( s[i] == '(' || s[i] == '*' ))
                ||  (s[i] == '*' && s[j] == '*');
        };
        auto DP = [&](auto &&self, int l, int r) -> int {
            if(l > r) return true; // for && (empty check)
            if(l == r) return s[l] == '*'; // len = 1
            if(l + 1 == r) return valid(l, r); // len = 2
            if(~dp[l][r]) return dp[l][r];

            // single block
            bool ans = valid(l, r) & self(self, l+1, r-1);

            // separate blocks
            for(int i = l; i < r; ++i) {
                ans |= self(self, l, i) & self(self, i+1, r);
            }

            return dp[l][r] = ans;
        };
        return DP(DP, 0, s.size()-1);
    }
};

LeetCode-678 Valid Parenthesis String