20. Valid Parentheses

Easy

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

Example 4:

Input: s = "([])"

Output: true

Constraints:

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'

Solutions

Approach: Stack

Time complexity: \(O(n)\)

Space complexity: \(O(n)\)

Way 1:

Algorithmic Way

Traverse the bracket string s.

• When encountering a left bracket, push the current left bracket into the stack;

• When encountering a right bracket, pop the top element of the stack (if the stack is empty, directly return false), and judge whether it matches. If it does not match, directly return false.

At the end of the traversal,

• if the stack is empty, it means the bracket string is valid, return true; otherwise, return false.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the bracket string .

Python

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        valid = ["()","{}","[]"]         # valid = {'()', '[]', '{}'}

        for ch in s:
            if ch in '({[':
                stack.append(ch)
            elif not stack or not (stack.pop() + ch in valid):
                return False
        return not stack

Way 2:

Using a dictionary or hashMap

PythonTypeScriptJavaScript

class Solution:
    def isValid(self, s: str) -> bool:
        mp = {
            '(':')',
            '[':']',
            '{':'}'
        }

        for ch in s:
            if ch in mp:
                stk.append(mp[ch])
            elif not stk or stk.pop()!=ch:
                return False

        return len(stk)==0

function isValid(s: string): boolean {
    const mp = new Map([
        ['(', ')'],
        ['[', ']'],
        ['{', '}'],
    ]);

    const stack = [];

    for (const c of s) {
        if (mp.has(c)) {
            stack.push(mp.get(c));
        } else if (stack.pop() !== c) {
            return false;
        }
    }
    return stack.length === 0;
}

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    let stk = []
    const mp = {'(':')','[':']','{':'}'}

    for (const ch of s){
        if(ch in mp) {
            stk.push(mp[ch])
        }
        else if (stk.length === 0 || stk.pop()!==ch) {
            return false
        }
    }
    return stk.length == 0
};

What is the difference between HashMap and HashTable in JavaScript?

Both Hash Tables and Hashmap provide a key/value functionality but there is a slight difference. Hashmap offers the ability of the keys to be of any data type, unlike Hash Tables where the keys can only be integers and strings. Also, Hashmaps can not be converted to JSON.

Read more