My easy to understand C++ solution with the stack idea(using a string to realize it)


  • 0
    Z

    Inspired by the stack idea, I use a string (temp) to simulate the function. If met a "(" or "[" or "{" , just append the character to temp, the other characters are“)”."]","}". If met a “)” or "]" or "}",take the last character of temp into compare, as we all know, the ascii value 40:"(" 41:“)” 91:"[" 93: "]" 123:"{" 125:"}", So if the characters are an valid pair, the absolute difference is less than 2 .if so, just remove the last character of temp, and continue comparing the remaining ones.

    class Solution {
    public:
        bool isValid(string s) {
            string temp="";
            int i=0;
            while(i<s.size())
            {
                if(s[i]=='('||s[i]=='['||s[i]=='{')
                {
                    temp+=s[i];
                    i++;
                }
                else
                {
                    if(temp.size()==0) return false;      //if temp is empty, means  “)”."]","}" has no partners
                    else if(abs(s[i]-temp[temp.size()-1])<=2) temp=temp.substr(0,temp.size()-1);   //remove the last character of temp
                    else return false;
                    i++;
                }
            }
            if(temp.size()!=0) return false;     //if temp is not empty,means  "(" or "[" or "{" has been left
            else return true;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.