【Leetcode】【240407】678. Valid Parenthesis String

It’s time to go back home, today’s in tomorrow lol
BGM：无地自容(黑豹乐队《黑豹》)

Descripition

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 singleright parenthesis ‘)’ or a single left parenthesis ‘(’ or an empty string “”.

Solution

Caution: Maybe take care of the pair order of ‘*’? Plz feel free to use queue instead and combine with stack.

Code

class Solution {
public:bool checkValidString(string s){typedef struct pair{char chat;int num;};stack<pair>pat;queue<pair>star;for(int i=0;i<s.length();++i){pair mid;mid.chat=s[i];mid.num=i;if(s[i]=='(') pat.push(mid);else if(s[i]=='*') star.push(mid);else{if(pat.empty()&&star.empty()) return false;else if(!pat.empty()) pat.pop();else if(pat.empty()&&(!star.empty())) star.pop(); }}stack<pair>new_star;while(!star.empty()){new_star.push(star.front());star.pop();}while(!pat.empty()){pair left=pat.top();if(!new_star.empty()){pair right=new_star.top();if(right.num<left.num) return false;else{new_star.pop();pat.pop();}}else return false;}return true;}
};