LeetCode - Valid Parentheses

Problem statement

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.

Problem statement taken from: https://leetcode.com/problems/valid-parentheses

Example 1:

Input: s = '()'
Output: true

Example 2:

Input: s = '()[]{}'
Output: true

Example 3:

Input: s = '(]'
Output: false

Example 4:

Input: s = '([)]'
Output: false

Example 5:

Input: s = '{[]}'
Output: true

Constraints:

- 1 <= s.length <= 10^4
- s consists of parentheses only '()[]{}'

Explanation

The problem can be solved by using a stack or by recursion. For a large string, building up a stack of recursive calls consumes memory temporarily and may take more space than an iterative solution.

We can use extra storage in the form of a stack and hashmap. Let's check the algorithm and solution.

Stack

- initialize stack st and i = 0.

- return true if the string is empty.

- Loop while i < 0
  - if s[i] == '(' || s[i] == '[' || s[i] == '{'

    // push the char to stack
    - st.push(s[i])

  - else if s[i] == ')' && !st.empty() && st.top() == '(' ||
            s[i] == '}' && !st.empty() && st.top() == '{' ||
            s[i] == ']' && !st.empty() && st.top() == '['

    // pop the top element if the current char is a closing brace provided
    // stack is not empty.
    - st.pop()

  - else

    // the string is not a valid parenthesis
    - return false

  i++

- return true if st.empty()

- return false.

C++ solution

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;

        if(s.size() == 0){
            return true;
        }

        int i = 0;
        while(i < s.size()){
            if( s[i] == '(' || s[i] == '[' || s[i] == '{' ){
                st.push(s[i]);
            } else if ( (s[i] == ')' && !st.empty() && st.top() == '(') ||
                        (s[i] == '}' && !st.empty() && st.top() == '{') ||
                        (s[i] == ']' && !st.empty() && st.top() == '[')
                      ){
                st.pop();
            } else {
                return false;
            }
            i++;
        }

        if(st.empty()) {
            return true;
        }

        return false;
    }
};

Golang solution

func isValid(s string) bool {
    st := []rune{}
	bracketsMap := map[rune]rune{
		')': '(',
		'}': '{',
		']': '[',
	}

	for _, v := range s {
		if len(st) == 0 {
			st = append(st, v)
			continue
		}

		if bracketsMap[v] == st[len(st)-1] {
			st = st[:len(st)-1]
		} else {
			st = append(st, v)
		}
	}

	return len(st) == 0
}

Javascript solution

var isValid = function(s) {
   let st = [];
   const legend = {
     '(': ')',
     '{': '}',
     '[': ']'
   };

   for (let i = 0; i < s.length; i++) {
     if (s[i] === '(' || s[i] === '{' || s[i] === '[') {
       st.push(s[i]);
     } else if (legend[st.pop()] !== s[i]) {
       return false;
     }
   }

   return st.length ? 0 : 1;
};

Dry Run

Let's dry-run our algorithm to see how the solution works.

Input:
s = ()[]{}

Step 1: stack<char> st;

Step 2: s.size() == 0
        s.size() = 6
        6 == 0
        false

Step 3: i = 0

Step 4: loop while i < 6
        0 < 6
        true

        // stack is empty
        st = []

        if s[i] == '(' || s[i] == '[' || s[i] == '{'
          true
          st.push(s[i])
          st.push( '(' )

                 top
                  |
          st = [ '(' ]

        i++
        i = 1

Step 5: loop while i < 6
        1 < 6
        true

               top
                |
        st = [ '(' ]

        if s[i] == '(' || s[i] == '[' || s[i] == '{'
          false

        else if (s[i] == ')' && !st.empty() && st.top() == '(')
          true
          st.pop()
          st = []

        i++
        i = 2

Step 6: loop while i < 6
        2 < 6
        true

        // stack is empty
        st = []

        if s[i] == '(' || s[i] == '[' || s[i] == '{'
          true
          st.push(s[i])
          st.push( '[' )

                 top
                  |
          st = [ '[' ]

        i++
        i = 3

Step 7: loop while i < 6
        3 < 6
        true

               top
                |
        st = [ '[' ]

        if s[i] == '(' || s[i] == '[' || s[i] == '{'
          false

        else if (s[i] == ']' && !st.empty() && st.top() == '[')
          true
          st.pop()
          st = []

        i++
        i = 4

Step 8: loop while i < 6
        4 < 6
        true

        // stack is empty
        st = []

        if s[i] == '(' || s[i] == '[' || s[i] == '{'
          true
          st.push(s[i])
          st.push( '{' )

                 top
                  |
          st = [ '{' ]

        i++
        i = 5

Step 9: loop while i < 6
        5 < 6
        true

               top
                |
        st = [ '{' ]

        if s[i] == '(' || s[i] == '[' || s[i] == '{'
          false

        else if (s[i] == '}' && !st.empty() && st.top() == '{')
          true
          st.pop()
          st = []

        i++
        i = 6

Step 10: loop while i < 6
        6 < 6
        false

Step 11: if st.empty()
           true

The answer is true.