Skip to main content

< Back to Data Structures and Algorithms

LeetCode 20 · Strings

Valid Parentheses

Whether every bracket closes in the right order, pushing openers onto a stack and popping one for each matching closer.

Step through it

Examples
Edge cases
s
  1. {0
  2. [1
  3. ]2
  4. }3

Step 0 of 4

Output

Running… play or step to the end.

The code

/**
 * Determine if a string contains valid sets of parentheses.
 * For example, "()" = true
 *              "()[]{}" = true
 *              "(]" = false
                "([)]" = false
                "{[]}" = true
 * @param {string} s
 * @return {boolean}
 */
const isValid = s => {
    // String is an odd number of characters, must be false.
    if (s.length % 2 !== 0) return false
    
    // Will keep track of open/close parentheses pairs using a stack data structure.
    const stack = []

    // O(n) loop over every character within the string.
    for (let i=0; i < s.length; i++) {
        // The top item in the stack
        const topItem = stack[stack.length-1]

        // Current character is an open parentheses.
        if (s[i] === '{' ||
            s[i] === '[' ||
            s[i] === '('
        ) {
            // Push the current character onto the stack.
            stack.push(s[i])
        /* Current character is a close parentheses, AND... 
           It's a match to the top item's open parentheses. */
        } else if (s[i] === '}' && topItem === '{' ||
                   s[i] === ']' && topItem === '[' ||
                   s[i] === ')' && topItem === '('
        ) {
            // A pair is created. Remove the top item from the top of the stack.
            stack.pop()
        // Neither an open parentheses, or a match.
        } else {
            // The string is NOT valid.
            return false
        }
    }
    
    // Stack still has items within it.
    if (stack.length) {
        // One or more parentheses remains unclosed, the string is NOT valid.
        return false
    }
    
    // The string is valid
    return true
}

View it on GitHub (opens in a new tab)