Topic describes

Given a only include a ‘(‘,’) ‘, ‘{‘,’} ‘, ‘/’, ‘ ‘the string s, determine whether a string is effective.

  • A valid string must meet the following requirements:

    • An open parenthesis must be closed with a close parenthesis of the same type.

    • The left parentheses must be closed in the correct order.

  • From:

    Force buckle (LeetCode) – valid parentheses

Train of thought

In order to use the stack

Take the following character string as an example

const str = "{([])}"
Copy the code

When an open parenthesis is encountered, there is no way to determine whether it is a match. When a close parenthesis is encountered, there is no way to determine whether it is a pair of parentheses.

It is better to make a mapping table of left and right parentheses in advance. When the left parentheses are encountered, put the corresponding close parentheses on the stack. As the expected target, when the close parentheses are encountered, take out the parentheses in the stack and judge whether the two parentheses are equal

const map = new Map([ ['(', ')'], ['[', ']'], ['{', '}'], ] // const testRightCh = const targetRight = map.get('(') const stack = [] stack.push(targetRight) // [')'] const testRightCh = Pop () === testRightChCopy the code

Matching failure:

  • When the closing parenthesis is matched during a string traversal
    • The stack is empty, indicating that the corresponding open parenthesis has not been present before, but is followed by a close parenthesis
    • The off-stack parentheses are not equal to the current parentheses
  • After iterating through the string
    • There are also elements in the stack indicating that some of the open parentheses do not have matching close parentheses

Code implementation ideas

  • Create the bracket mapping table
  • Iterate over the string, fetching each character
  • Check that it is an open parenthesis, and the corresponding close parenthesis is pushed
  • Is a right parenthesis
    • Stack empty, failed
    • Unstack element not equal to closing parenthesis, failed
  • At the end of the loop, check whether the stack is empty
    • If the stack is empty, all matches are successful.
    • Otherwise, some parentheses do not match and fail
/** * @param {string} s String to be matched * @return {Boolean} Matching result */ const isValid = function (s) {// Left-right bracket mapping table const map = new Map ([[' (', ') '], [' [', ']], [' {', '} ']]) / / storage left parenthesis corresponding right parenthesis const stack = [] / / traversal string, For (const c of s) {// open parenthesis (map.has(c)) {// Open parenthesis (map.has(c)) { It is ok to directly compare stack. Push (map) get (c)) met right parenthesis} else {/ / / / the stack is empty or the stack elements and right brace does not match the if current (stack. The length = = = 0 | | stack. Pop ()! Return stack.length === 0? true : false }Copy the code