“This is the 7th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Topic:

20. Valid brackets

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

A valid string must meet the following requirements:

  1. An open parenthesis must be closed with a close parenthesis of the same type.
  2. The left parentheses must be closed in the correct order.

 

Example 1:

Input: s = "()" output: trueCopy the code

Example 2:

Input: s = "()[]{}" Output: trueCopy the code

Example 3:

Input: s = "(]" Output: falseCopy the code

Example 4:

Input: s = "([)]" Output: falseCopy the code

Example 5:

Input: s = "{[]}" Output: trueCopy the code

 

Tip:

  • 1 <= s.length <= 104
  • sOnly by brackets'[] {} ()'composition

Train of thought

  1. First, we establish the mapping relationship between each type of left and right parentheses through the map object.

  2. Create an empty array stack to hold the open parenthesis;

  3. Iterate through the string, determine if the current position is an open parenthesis, push it directly into the stack;

  4. If the current position is a close parenthesis, we need to determine:

    (1) Whether there is an open parenthesis before it;

    (2) whether the last open parenthesis before it matches the current close parenthesis;

  5. If the condition is met, delete the last element from the current stack, otherwise the match fails, and return false.

  6. At the end of the loop, check if there are any remaining open parentheses, if not, the match is successful.

Implementation:

/ * * *@param {string} s
 * @return {boolean}* /
var isValid = function(s) {
    const n = s.length;
    // Establish the corresponding relationship first
    let map = new Map(a); map.set("(".")");
    map.set("{"."}");
    map.set("["."]");

    let stack = [];
    for (let i = 0; i < n; i++) {
      let cur = s.charAt(i);
      // Check whether open parenthesis is used
      if (map.has(cur)) {
          stack.push(cur);
      } else {
          let last = stack.pop();
          if(map.get(last) ! == cur) {return false; }}}// If the left parenthesis does not match the left parenthesis, the left parenthesis does not match the left parenthesis
    return stack.length === 0;
};
Copy the code

If you understand it, you can click on it and see you in the next topic. If there is no accident after the article will be in this form, there are good suggestions welcome to comment area.