Leetcode/Valid_Parenthesis_String.cpp at main · sazzadkhan20/Leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution
{
public:
    bool checkValidString(string s)
    {
        stack<pair<char, int>> bracketStack;
        stack<pair<char, int>> starStack;
        for (int i = 0; i < s.length(); i++)
        {
            if (s[i] == '(')
                bracketStack.push({s[i], i});
            else if (s[i] == ')')
            {
                if (!bracketStack.empty() && bracketStack.top().first == '(')
                    bracketStack.pop();
                else if (!starStack.empty() && starStack.top().first == '*')
                    starStack.pop();
                else
                    return false;
            }
            else
                starStack.push({s[i], i});
        }
        while (!bracketStack.empty() && !starStack.empty())
        {
            if (bracketStack.top().second < starStack.top().second)
            {
                bracketStack.pop();
                starStack.pop();
            }
            else
                return false;
        }
        if (!bracketStack.empty() && starStack.empty())
            return false;
        return true;
    }
};