Home LeetCode-678 Valid Parenthesis String
Post
Cancel

LeetCode-678 Valid Parenthesis String

Description

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

Constraints

\(1 \le n \le 100\)

Solution

一眼区间DP。除了要求细心以外没啥特别的,只是个人想复习一下区间DP。

Code

class Solution {
public:
    bool checkValidString(string s) {
        bool dp[103][103] {};
        bool vis[103][103] {};
        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 i, int j) {
            // empty, for loop check (self && self)
            if(i > j) return true;
            if(i == j) return s[i] == '*';
            if(i + 1 == j) return valid(i, j);
            if(vis[i][j]) return dp[i][j];
            shared_ptr<void> _ {nullptr, [&](auto){vis[i][j] = true;}};

            // single block
            if(valid(i, j) && self(self, i+1, j-1)) {
                return dp[i][j] = true;
            }

            // separate blocks
            // NOTE: k!=j
            for(int k = i; k < j; ++k) {
                if(self(self, i, k) && self(self, k+1, j)) {
                    return dp[i][j] = true;
                }
            }
            return dp[i][j] = false;
        };
        return DP(DP, 0, s.size()-1);
    }
};

LeetCode-678 Valid Parenthesis String

This post is licensed under CC BY 4.0 by the author.
Contents