20. Valid Parentheses(LeetCode note)

Topics : String , Stack

Input: Given a string s containing just the characters ( ) [ ] { }，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.

Output: If it is a valid parentheses , return true otherwise , return false.

Example: Input: s = “()[]{}” Output: true

Input: s = “([])” Output: true

Input: s = “([)]” Output: false

Approach

solution :(Stack)

#include <string>
#include <stack>
using namespace std;

class Solution {
public:
    bool isValid(string s) {
        stack<char> stack;
        for(char ch: s){
            if(ch == '(' || ch == '[' || ch == '{'){
                stack.push(ch);
            }else {
                if (stack.empty()){
                    return false;
                }
                char top = stack.top();
                stack.pop();
                if(ch == ')' && top != '('){
                    return false;
                }
                 if(ch == ']' && top != '['){
                    return false;
                }
                 if(ch == '}' && top != '{'){
                    return false;
                }
            }
        }
        return stack.empty();
    }
};

Complexity Analysis

• Time complexity: O(n).
• Space complexity: O(n).