22. Valid Parenthesis String

Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid.

The following rules define a valid string:

• 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 "".

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "(*)"
Output: true

Example 3:

Input: s = "(*))"
Output: true

Solution: (Recursion)

class Solution
{
public:
    bool checkValid(string s, int pos, int co, int cc)
    {
        if (pos == s.length())
        {
            if (co == cc)
            {
                return true;
            }
            return false;
        }

        if (cc > co)
        {
            return false;
        }

        if (s[pos] == '(')
        {
            return checkValid(s, pos + 1, co + 1, cc);
        }
        else if (s[pos] == ')')
        {

            return checkValid(s, pos + 1, co, cc + 1);
        }
        else
        {
            return checkValid(s, pos + 1, co + 1, cc) || checkValid(s, pos + 1, co, cc + 1) || checkValid(s, pos + 1, co, cc);
        }
    }

    bool checkValidString(string s)
    {
        return checkValid(s, 0, 0, 0);
    }
};

Solution: (Using Two Stacks)

class Solution
{
public:
    bool checkValidString(string s)
    {

        stack<char> open;
        stack<char> star;

        for (int i = 0; i < s.length(); i++)
        {

            if (s[i] == '(')
            {
                open.push(i);
            }
            else if (s[i] == '*')
            {
                star.push(i);
            }
            else
            {
                if (!open.empty())
                {
                    open.pop();
                }
                else if (!star.empty())
                {
                    star.pop();
                }
                else
                {
                    return false;
                }
            }
        }

        while (!open.empty())
        {
            if (!star.empty() && star.top() > open.top())
            {
                open.pop();
                star.pop();
            }
            else
            {
                return false;
            }
        }

        return true;
    }
};

Solution:(Optimized)

class Solution
{
public:
    bool checkValidString(string s)
    {

        int count = 0;

        for (int i = 0; i < s.length(); i++)
        {
            if (s[i] == '(' || s[i] == '*')
            {
                count++;
            }
            else
            {
                count--;
            }

            if (count < 0)
            {
                return false;
            }
        }
        
        count = 0;
        for (int i = s.length() - 1; i >= 0; i--)
        {
            if (s[i] == ')' || s[i] == '*')
            {
                count++;
            }
            else
            {
                count--;
            }
            if (count < 0)
            {
                return false;
            }
        }

        return true;
    }
};