<p>Given a string <code>s</code> containing only three types of characters: <code>&#39;(&#39;</code>, <code>&#39;)&#39;</code> and <code>&#39;*&#39;</code>, return <code>true</code> <em>if</em> <code>s</code> <em>is <strong>valid</strong></em>.</p>

<p>The following rules define a <strong>valid</strong> string:</p>

<ul>
	<li>Any left parenthesis <code>&#39;(&#39;</code> must have a corresponding right parenthesis <code>&#39;)&#39;</code>.</li>
	<li>Any right parenthesis <code>&#39;)&#39;</code> must have a corresponding left parenthesis <code>&#39;(&#39;</code>.</li>
	<li>Left parenthesis <code>&#39;(&#39;</code> must go before the corresponding right parenthesis <code>&#39;)&#39;</code>.</li>
	<li><code>&#39;*&#39;</code> could be treated as a single right parenthesis <code>&#39;)&#39;</code> or a single left parenthesis <code>&#39;(&#39;</code> or an empty string <code>&quot;&quot;</code>.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> s = "()"
<strong>Output:</strong> true
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> s = "(*)"
<strong>Output:</strong> true
</pre><p><strong class="example">Example 3:</strong></p>
<pre><strong>Input:</strong> s = "(*))"
<strong>Output:</strong> true
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 100</code></li>
	<li><code>s[i]</code> is <code>&#39;(&#39;</code>, <code>&#39;)&#39;</code> or <code>&#39;*&#39;</code>.</li>
</ul>

class Solution {
public:
    bool checkValidString(string s) {
        TryCombinationsAndCheckValid(s, 0, 0, 0);
        return is_valid_;
    }
private:
    void TryCombinationsAndCheckValid(const string& s, const int idx, const int open, const int close) {
        if (is_valid_) { return; }
        if (open == close && idx == s.length()) {
            is_valid_ = true;
            return;
        }
        if (close > open) { 
            return;
        }
        if (idx == s.length()) { return; }
        // if (dp_.contains({idx, open - close})) {
        //     false;
        // }

        if (s.at(idx) == '(') {
            TryCombinationsAndCheckValid(s, idx + 1, open + 1, close);
        } else if (s.at(idx) == ')') {
            TryCombinationsAndCheckValid(s, idx + 1, open, close + 1);
        } else {
            if (dp_.contains({idx, open - close, '*'})) { return; }
            TryCombinationsAndCheckValid(s, idx + 1, open, close);
            dp_.insert({{idx, open - close, '*'}, false});

            if (dp_.contains({idx, open - close + 1, '('})) { return; }
            TryCombinationsAndCheckValid(s, idx + 1, open + 1, close);
            dp_.insert({{idx, open - close + 1, '('}, false});

            if (dp_.contains({idx, open - close - 1, ')'})) { return; }
            TryCombinationsAndCheckValid(s, idx + 1, open, close + 1);
            dp_.insert({{idx, open - close - 1, ')'}, false});
        }
    }

bool is_valid_ = false;
std::map<std::tuple<int, int, char>, bool> dp_;
};

// keep a count of *.
// reduce this by 1 whenever close exceeds open, and increment open by 1.

// class Solution {
// public:
//     bool checkValidString(string s) {
//         int open = 0, close = 0, wild = 0;
//         for (const char& c : s) {
//             if (c == '(') {
//                 ++open;
//             } else if (c == ')') {
//                 ++close;
//                 if (close > open) {
//                     if (wild <= 0) { return false; }
//                     --wild;
//                     ++open;
//                 }
//             } else {
//                 ++wild;
//             }
//         }
//         std::cout << "open, close, wild are: " << open << " " << close << " " << wild;
//         if (close + wild >= open) { return true; }
//         return false;
//     }
// };

// keep a count of *.
// reduce this by 1 whenever close exceeds open, and increment open by 1.
// * should act as open whenever close > open.
// It should act as close at the end, when there are more open than close.

// (*((*(*))
// ()(()())
// "(((((*(()((((*((**(((()()*)()()()*((((**)())*)*)))))))(())(()))())((*()()(((()((()*(())*(()**)()(())"
14060