Valid parentheses

Given a string, the string contains ( ) [ ] { }. Write a method to check if the string is valid

 

The string is valid if:

• The input string is empty
• Open brackets are closed by the same type of brackets
• Open brackets are closed in the correct order

Example 1

Input: ({})

Output: true

Example 2

Input: [)

Output: false

Before writing a code, let's see possible inputs it will help to see all corner cases.

] - invalid because there is no opening bracket

( - invalid because there is no corresponding closing bracket

(] - invalid because there is no corresponding opening bracket

()( - invalid because there is no corresponding closing bracket. ( - was not closed

([)] - invalid because there is no corresponding opening bracket. [) - parentheses don't match

Based on invalid inputs, we see:

• if we see a closing bracket before should be the corresponding opening bracket
• each opened bracket should have a closed bracket
  • opening and closing brackets should match

Now let's see some valid scenarios:

"" - empty input

() - all brackets were closed in the correct order

(){} - all brackets were closed in the correct order

({[]}) - all brackets were closed in the correct order

Approach

To solve this problem, we will use the stack data structure.

• if we see an opening bracket
  • we push the bracket to the stack
• if we see a closing bracket
  • we check if the stack is empty
    • if the stack is empty, it means there are no opening brackets
  • if the stack is not empty, we check that do opening and closing brackets match
• at the end, we check if the stack is empty.
  • if the stack is not empty, it means some open brackets were not closed.
  • if the stack is empty, it means all brackets were closed in the correct order

Code

    public bool IsValidParentheses(string parentheses)
    {
        if (string.IsNullOrEmpty(parentheses))
        {
            return true;
        }

        var stack = new Stack<char>();
        foreach (char bracket in parentheses)
        {
            if (bracket == '(' || bracket == '[' || bracket == '{')
            {
                stack.Push(bracket);
            }
            else
            {
                if (stack.Count == 0)
                {
                    return false;
                }

                char last = stack.Pop();
                switch (bracket)
                {
                    case ')':
                    {
                        if (last != '(')
                        {
                            return false;
                        }

                        break;
                    }
                    case ']':
                    {
                        if (last != '[')
                        {
                            return false;
                        }

                        break;
                    }
                    case '}':
                    {
                        if (last != '{')
                        {
                            return false;
                        }

                        break;
                    }
                }
            }
        }

        if (stack.Count != 0)
        {
            return false;
        }

        return true;
    }

The time complexity is O(n).