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.

//Added for fast I/O operations

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;

}
};