A solution for leetcode problem 20 “valid parentheses”



This content originally appeared on DEV Community and was authored by hallowaw

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






This content originally appeared on DEV Community and was authored by hallowaw