# Day 16 of 30-Day LeetCode Challenge

--

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:

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

static auto x = [](){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return nullptr;
}();

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

//method 1 : checking for all possible combination of * value
//O(3^n) time & O(1) space : TIME LIMIT EXCEEDED

//method 2 : dynamic programming approach
//O(n³) time & O(n²) spce
//DP solution will be updated

//*** MOST EFFICIENT METHOD ***
//method 3 : greedy approach -> beats 100 % of other cpp solutions
//O(n) time & O(n) space
stack<char> st;

for(int i=0;i<s.size();++i){
if(s[i]==’(‘||s[i]==’*’) st.push(s[i]);
else if(s[i]==’)’){
if(st.empty()||st.top()==’)’) return false;
else if(st.top()==’(‘) st.pop();
else if(st.top()==’*’){
int starCount = 0;
while(!st.empty()&&st.top()==’*’){
++starCount;
st.pop();
}
if(st.empty()||st.top()==’)’) {
if(starCount>0) — starCount;
else return false;
}
else if(st.top()==’(‘) st.pop();
while(starCount>0){
st.push(‘*’);
— starCount;
}
}
}
}

while(!st.empty()){
if(st.top()==’*’){
//check if there exists a ‘(‘
int starCount = 0;
while(!st.empty()&&st.top()==’*’){
++starCount;
st.pop();
}
if(st.empty()){
— starCount;
while(starCount>0){
st.push(‘*’);
— starCount;
}
}else if(st.top()==’(‘){
st.pop();
— starCount;
while(starCount>0){
st.push(‘*’);
— starCount;
}
}else return false;

}else return false;
}
return true;

}
};