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);
}
};