20. Valid Parentheses

Difficulty Level : Easy

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.
 

Example 1:

Input: s = "()"
Output: true
Example 2:

Input: s = "()[]{}"
Output: true
Example 3:

Input: s = "(]"
Output: false
 

Constraints:

1 <= s.length <= 104
s consists of parentheses only '()[]{}'.

Solution

This problem is too much famous so I'm not going to explain about the problem itself. But, I'd like to mention that if we are preparing for live coding, practicing like a pro is important.

#include <string>

using namespace std;

class Stack{
private:
    char* arr;
    int top;
    int size;
public:
    Stack(int size) : size(size), top(-1) { arr = new char[size]; }
    ~Stack(){ delete[] arr; }

    void push(char s){ if(top < size - 1) arr[++top] = s; }
    char pop(){ if(top >= 0) return arr[top--]; else return '\0'; }
    char peek(){ if(top >= 0) return arr[top]; else return '\0'; }
    bool isEmpty(){ return top < 0; }
};

class Solution {
private:
    Stack* stack;
public:
    bool isValid(string s);   
    bool isPair(char c1, char c2);
};

bool Solution::isPair(char c1, char c2) {
    return (c1 == '(' && c2 == ')') || (c1 == '[' && c2 == ']') || (c1 == '{' && c2 == '}');
};

bool Solution::isValid(string s){
    this->stack = new Stack(s.size());
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
            (*this->stack).push(s[i]);
        } else {
            if ((*this->stack).isEmpty() || !isPair((*this->stack).pop(), s[i])) {
                return false;
            }
        }
    }

    if (!(*this->stack).isEmpty()) {
        return false;
    }

    return true;
};