20.Valid Parentheses

Valid Parentheses

Problem Description

This article talks about a problem famously known as Valid Parentheses. True to its name the problem deals with finding whether a given string has a valid set of parentheses. A parenthesis is said to be balanced if each left parenthesis has its respective right parenthesis to match its pair in a well-nested format.

In computer science, valid parentheses(balanced parentheses) are a notation used to simplify expressions written in an operator-precedence parser by allowing the programmer to explicitly mark the operator precedence and associativity of a given expression.

 

Problem Description

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

We are going to use the stack data structure to solve this problem. If you guys are not familiar with stack data structure you can follow the linked article

Code:

Runtime complexity: O(N)

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    if(!s || s.length <= 1){
        return false;
    }
    
    let stack = [];
    let map = {
        '(':')',
        '[':']',
        '{':'}',
    }
    
    for(let i=0;i< s.length;i++){
        if(map[s[i]]){
            stack.push(map[s[i]])
        }else{
            if(stack.pop() != s[i]){
               return false
            }
        }
    }
    
    return stack.length > 0 ? false : true;
};

Resources:

https://github.com/PraveenMistry/leetCode

https://medium.com/@praveenmistry/stack-javascript-part-1-15f9e6ebecd5

Conclusion

That’s all folks! In this post, we solved LeetCode problem #20.Valid Parentheses

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!