DEV Community

hallowaw
hallowaw

Posted on

A solution for leetcode problem 20 "valid parentheses"

Image description

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
        }
    }
};





Enter fullscreen mode Exit fullscreen mode

Top comments (0)