Is it possible to convert this recursive solution to DP for "Valid Parenthesis String" problem?

Question

The context: I am trying to learn dynamic programming by coming up with a recursive solution and then caching the results of sub-problems.

I've been really struggling with this LeetCode problem.

Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules:

Any left parenthesis '(' must have a corresponding right parenthesis ')'. Any right parenthesis ')' must have a corresponding left parenthesis '('. Left parenthesis '(' must go before the corresponding right parenthesis ')'. '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string. An empty string is also valid.

Example 1:

Input: "()", Output: True

Example 2:

Input: "(*)", Output: True

Example 3:

Input: "(*))", Output: True

I managed to come up with a recursive solution that seems to work. However, I am not able to convert it to DP, I don't even understand where I should start or what I should be caching, i.e. I don't see how the results of the recursion sub-trees are the same for different subproblems. I am aware of an existing DP solution. But I am not able to relate it to my recursive one. Is it even possible to convert this particular solution to DP? I would really appreciate suggestions.

Here is my code:

class Solution {
public:
    bool checkValidString(string s) {
        stack<int> paren_stack;
        int ind = 0;
        return check_valid_rec(s, ind, paren_stack);
    }

private:
    bool check_valid_rec(string& s, int ind, stack<int> paren_stack) {

        if (ind >= s.size())
            return paren_stack.empty();

        while (s[ind] != '*' && ind < s.size()) {
            if (s[ind] == '(')
                paren_stack.push('(');
            else {
                if (!paren_stack.empty() && paren_stack.top() == '(')
                    paren_stack.pop();
                else return false;
            }
            ind++;
        }

        if (ind >= s.size())
            return paren_stack.empty();

        // if '*', there are three options
        // 1. ignore '*'
        bool ignore = check_valid_rec(s, ind + 1, paren_stack);
        // 2. replace with '('
        s[ind] = '(';
        bool left_replace = check_valid_rec(s, ind, paren_stack);
        // 3. replace with ')'
        s[ind] = ')';
        bool right_replace = check_valid_rec(s, ind, paren_stack);

        if (ignore || left_replace || right_replace)
            return true;
        else 
            return false;
    }
};

Answer 1

At first, your stack only contain '(' so can simply be a counter.

s is "nearly" constant so you have only ind, left_counter as variable for dp:

std::vector<std::vector<bool>> dp(s.size() + 1, std::vector<bool>(s.size(), false));

and dp[0][0] got your final result.

Now initialization:

if (ind >= s.size())
    return paren_stack.empty();

so dp[s.size()][0] = true;

Now, passing from one column to the next (prev in our case :) ) (trying to keep your logic as much as I can):

switch (s[ind]) {
    case '*':
        dp[ind][j] = dp[ind + 1][j] /* Empty */
                   | (j > 0 && dp[ind + 1][j - 1]) /* ) */
                   | (j + 1 < s.size() && dp[ind + 1][j + 1]) /* ( */
                   ;
                   break;
    case '(': dp[ind][j] = (j + 1 < s.size() && dp[ind + 1][j + 1]); break;
    case ')': dp[ind][j] = (j > 0 && dp[ind + 1][j - 1]); break;
}

Final result:

bool is_balanced(const std::string& s)
{
    if (s.empty()) return true;

    std::vector<std::vector<bool>> dp(s.size() + 1, std::vector<bool>(s.size(), false));

    dp[s.size()][0] = true;

    for (int ind = s.size() - 1; ind >= 0; --ind) {
        for (std::size_t j = 0; j != s.size(); ++j) {
            switch (s[ind]) {
                case '*':
                    dp[ind][j] = dp[ind + 1][j] /* Empty */
                               | (j > 0 && dp[ind + 1][j - 1]) /* ) */
                               | (j + 1 < s.size() && dp[ind + 1][j + 1]) /* ( */
                               ;
                               break;
                case '(': dp[ind][j] = (j + 1 < s.size() && dp[ind + 1][j + 1]); break;
                case ')': dp[ind][j] = (j > 0 && dp[ind + 1][j - 1]); break;
            }
        }
    }
    return dp[0][0];
}

Demo

Answer 2

Your solution is an example of backtracking. It does not obey the overlapping subproblems property. The dp solution link you shared contains a correct approach. That is also easy to implement as recusrion as well as dp.

If you still want to stick to your approach(or something similar), you have to adjust your way to obey the overlapping subproblems property. I have an approach in mind which you can perhaps look into:

1. Start from the end of the given string.
2. Instead of a stack, maintain the count of left and right paranthesis.
3. Psudocode for recursion:
bool foo(pos,count_left_paranthesis,count_right_paranthesis):
    if count_left_paranthesis >  :
        return false;
    if (pos < 0)
        return count_left_paranthesis == count_right_paranthesis;
    if string[pos] == '(':
        return foo(pos-1,count_left_paranthesis+1,count_right_paranthesis);
    else if string[pos] == '):
        return foo(pos-1,count_left_paranthesis,count_right_paranthesis+1);
    else: // string[pos] = '*'
        return foo(pos-1,count_left_paranthesis,count_right_paranthesis) 
                  || foo(pos-1,count_left_paranthesis,count_right_paranthesis+1) 
                  || foo(pos-1,count_left_paranthesis+1,count_right_paranthesis)
4. Memoize the results of the subproblems.

There are easier solutions available though.

I tried the above out myself and here's a working solution. Surprisingly it even got accepted.

class Solution {
public:
    map<vector<int>,bool> dp;
    bool foo(const string& s, int pos, int lc, int rc)
    {
        if (lc > rc) return false;
        if (pos<0)
        {
            return lc == rc;
        }
        vector<int> v = {pos,lc,rc};
        if (dp.find(v) != dp.end()) return dp[v];
        if (s[pos] == '(')
        {
            return dp[v] = foo(s,pos-1,lc+1,rc);
        }
        else if (s[pos] == ')')
        {
            return dp[v] = foo(s,pos-1,lc,rc+1);
        }
        else
        {
            return dp[v] = (foo(s,pos-1,lc,rc) || foo(s,pos-1,lc+1,rc) || foo(s,pos-1,lc,rc+1));
        }
    }
    bool checkValidString(string s) {
        return foo(s,s.size()-1,0,0);
    }
};

• another quick optimization may be to use a vector to memoize instead but i'm lazy.
• well you can even start from the start of the string. Starting from the back was easier to analyze for me

Note: This by no means is the most efficient method to solve the problem, this is just to help the OP with a recursive solution and then come up with a dp solution with the means of memoization (or "caching the results of sub-problems")