Solution by teamskiy


  • 1
    T

    Let the parentheses ‘(‘, ‘{‘ and ‘[‘ be called “opening parentheses” and parentheses ‘)’, ‘}’ and ‘]’ be called “closing parentheses”. Then the problem is clearly about having a track of the last unclosed opening parenthesis and when it is closed by appropriate closing parenthesis, we should close the previously appeared opening parenthesis. So, we should somewhere store this opening parentheses by their order of appearance in the string and delete them as we close them, we could use a vector, but since we only deal with the last opening parenthesis, we can use the stack instead. There are only 2 possibilities have an invalid string as we go through it character by character:

    1. If there are no opening parentheses to close, in other words, if the stack is empty.
    2. If we close the last opening parenthesis with invalid closing parenthesis.
      So, here is the code:
    class Solution {
    public:
        bool isValid(string s) {
            stack<char> z;
            for (auto c : s) {
                if (c == '(' || c == '{' || c == '[') z.push(c); // ADDING THE OPENING PARENTHESES TO THE STACK AS THEY APPEAR
                else if (z.empty()) return false; // HERE IS THE POSSIBILITY 1 CHECKED
                if (c == ')') {                  //////////////////////////////////////////////
                    if (z.top() == '(') z.pop(); //                                          //
                    else return false;           //                                          //
                }                                //                                          //
                if (c == '}') {                  // HERE THE POSSIBILITY 2 IS CHECKED,       //
                    if (z.top() == '{') z.pop(); // IF THE CLOSING PARENTHESIS IS CORRECT,   //
                    else return false;           // IT DELETES THE LAST OPENING PARENTHESIS, //
                }                                // OTHERWISE, THE STRING IS INCORRECT AND   //
                if (c == ']') {                  // IT RETURNS FALSE                         //
                    if (z.top() == '[') z.pop(); //                                          //
                    else return false;           //                                          //
                }                                //////////////////////////////////////////////
            }
            return z.empty();
        }
    };
    

    Complexity Analysis:
    • Time complexity: O(n), where n – length of the string. Every character was operated only once.
    • Space complexity: O(n), where n – length of the string. The extra space required depends on the number of the opening parentheses.


Log in to reply
 

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