Valid Parentheses

String, Stack Approach

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

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.

2. Open brackets must be closed in the correct order.

3. 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 '()[]{}'.

Solutions

public class Solution {
    public bool IsValid(string s) {
        
        if(s.Length%2!=0){
            return false;
        }
        
        Stack<char> braces=new Stack<char>();
        foreach( char ch in s){
            
                if(braces.Count==0){
                    braces.Push(ch);
                    continue;
                }
 
            if(ch==')' && braces.Peek()=='('){
                braces.Pop();
            }
            else if(ch=='}' && braces.Peek()=='{'){
                braces.Pop();
            }
            else if(ch==']' && braces.Peek()=='['){
                braces.Pop();
            }
            else{
                 braces.Push(ch);
            }
            
        }
        
        return braces.Count==0;
    }
}

Complexity

• Time Complexity: O(1)

• Auxiliary Space: O(1)