This content originally appeared on DEV Community and was authored by hallowaw
First we need find out what is the correct corresponding relationship for parentheses?
it is not "}" must follow "{" very closely,and we allow that situation that "{[()]}" and "{}" even "{[]}()"
And the true rule we need follow is that each ending parentheses like "),},]"need fit to the last beginning parentheses so that we have the following codes with very detailed explainations:
class Solution {
public://the requirement of the problem is to check if the parentheses is conformed by the rules and
//the rule is that the ending parenthese must correspond to the last beginning parentheses
bool isValid(string s) {
vector<char> vec1;//define a vector
bool result=false;//the defualt result it false
if(s.length()%2==1){
return false;
}//if the length of s is odd,then it can not have the same number of beginning parenthese and ending parenthese
for (int i = 0; i < s.length(); i = i + 1)
{
char c = s[i];//we let each element in s euqate c,
if (c == '(' || c == '{' || c == '[') {
vec1.push_back(c);//and if c equate the beginning parentheses we sotre it in vec1
}
else{
if(vec1.empty())
{return false;//if c do not equate beginning psrentheses and c is NULL return false
}
else if(c == ')' || c == '}' || c == ']') {
//if c equate ending psrentheses
int num=vec1.size()-1;//to make vec[num]is the last element of the vec1
if((vec1[num]=='{'&&s[i]=='}')||(vec1[num]=='['&&s[i]==']')||(vec1[num]=='('&&s[i]==')')){
result=true;
vec1.pop_back();//if the c is ending parentheses and have the corresponding relationship with the last begining parenthese ,we let result equate true and delete the last beginning parenthese from the vec1
}
else{
return false;
}
}
}
}
if(vec1.empty()){
return result;
//if when we finish such operations and there is not elements in the vec1 and each begining parentheses and ending parentheses have correct relation in correct order then output the "true " result.
}
else{
return false;//,maybe there are some elements remain in vec1 so must return false
}
}
};
This content originally appeared on DEV Community and was authored by hallowaw
hallowaw | Sciencx (2024-07-15T10:25:03+00:00) A solution for leetcode problem 20 “valid parentheses”. Retrieved from https://www.scien.cx/2024/07/15/a-solution-for-leetcode-problem-20-valid-parentheses/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.