Valid Parentheses

Leave a reply

[tabby title=”Task”]

Given a string 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.

Note that an empty string is also considered valid.

Example 1:

Input:

 "()"

Output:

 true

Example 2:

Input:

 "()[]{}"

Output:

 true

Example 3:

Input:

 "(]"

Output:

 false

Example 4:

Input:

 "([)]"

Output:

 false

Example 5:

Input:

 "{[]}"

Output:

 true

This problem was taken from Leetcode

[tabby title=”Solution”]

The solution:

Let’s look at the simplest scenario where we have only one type of brackets: ‘(‘ and ‘)’. Then all that we need to do in order to figure out if each bracket has corresponding closing bracket is to put each opening bracket into a stack, and pop one bracket when we see closing bracket.

Ideally if the brackets are “normalized” (all of the open one have corresponding closing brackets) we will end up with empty stack.

in example :

( ( ) ( ) ( ( ) ) )
1 2  3  4 5  6  7  8  9  10

so here are all 10 steps:

steps  stack
1          (
2          (  (
3         (
4         (  (
5         (
6         (  (
7         (  (  (
8         (  (
9         (
10

Immediately it becomes clear that if the string  length is not an even number, it automatically becomes invalid. So we could do this check in the very beginning (lines 9 and 10)  below.

So let’s look at the current example where we have 3 different tags: ‘{}’, ‘()’, ‘[]’

The rule for a valid string is:
open tags:
– we could have as many open tag as we want. i.e. : ({[[ ...
closing tags:
– every closing tag should match previously opened tag ([]) – valid, ([)] – invalid.

So now we know the rules, let’s write the code.

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    
    var input = s.split('');
    
    if(input.length % 2 != 0)
        return false;
    
    var stack = [];

    var tagIndex = {
        '(': 0,
        ')': 1,
        '{': 2,
        '}': 3,
        '[': 4,
        ']': 5
    };        


    for(var q=0;q < input.length; q++) {
        var symbol = input[q];
        var tagType = (tagIndex[symbol] % 2); // 0 - open, 1 - close
        if(tagType == 0) {
            stack.push(symbol);
        }
        else {
            // this is a closing tag, make sure that it follows the rules
            lastTag = stack.pop();            
            lastTagIndex = tagIndex[lastTag];
            if( tagIndex[symbol] != lastTagIndex + 1 )
                return false;
        }
    }
    
    if(stack.length > 0)
        return false;
    return true;
};

 

what we just did:
– lines 9 and 10: we check if the length of the string is odd and return false immediately if so.
– we added tagIndex object where every bracket has it’s index which will help us to identify if we have the open or closing bracket.
– If it is open bracket, we just putting it inside the stack.
– if this is a close bracket, we are using the newly created  tagIndex to figure out if this is the right closing bracket from the same type. Simply following the rule that we described above (lines 32 -35)  `if( tagIndex[symbol] != lastTagIndex + 1 )` Basically we check if the previous opening tag in the stack is of the same type of the current closing tag.

[tabbyending]

Leave a Reply