Question

You are given a string s consisting of the following characters: '(', ')', '{', '}', '[' and ']'.

The input string s is valid if and only if:

1. Every open bracket is closed by the same type of close bracket.

2. Open brackets are closed in the correct order.

3. Every close bracket has a corresponding open bracket of the same type.

Return true if s is a valid string, and false otherwise.

Example 1

Input: s=’[]’

Output: true

Example 2

Input: s=’{}(}(’

Output: false

Approach

Intuition

A parenthesis is called valid if and only if they are in pair like {} or [] or (). If either one of them is missing then they are not valid. So we have to keep track of open parenthesis and if there is any close parenthesis then we remove the pair. To do this we store the open parenthesis in stack and if their exist a close parenthesis for the same open parenthesis then we will pop the open parenthesis.

Algorithm

1. Check if length of given is string is even or odd. If odd then return false.

2. Create a stack.

3. For index i from 0 to length of given string:

   1. Push the open parenthesis and continue.

   2. If the char is not open parenthesis, then find the top element of stack (last element of array)

   3. If there exist a pair of parenthesis like {} or () or [] then pop the top element from stack

   4. Else push the close parenthesis in stack.

4. After then loop, return true or false based on the length of stack. If 0 then return true or else false.

Dry Run

Solution (JS code)

class Solution {
    /**
     * @param {string} s
     * @return {boolean}
     */
    isValid(s) {
        const n = s.length;
        if (n%2 !== 0) return false

        const stack = [];

        for (let c of s) {
            console.log("char is ", c)
            if (c === '{' || c === '[' || c === '(') {
                stack.push(c)
                continue;
            }
            console.log("stack is ", stack)

            const size = stack.length;
            console.log("size of stack : ", size)
            if (size == 0) {
                return false;
            }
            const top = stack[size-1];
            console.log("top is ", top)

            if (top === '[' && c === ']') {
                stack.pop()
            }
            else if (top === '{' && c === '}') {
                stack.pop()
            }
            else if (top === '(' && c === ')') {
                stack.pop()
            }
            else {
                stack.push(c)
            }
        }

        return stack.length === 0 ? true : false;
    }
}

Time Complexity

O(n)

Space Complexity

O(n)