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

[B] [C] [D]

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

This question asks us to determine whether the parentheses in the input string all correspond one to one

So when we see a close parenthesis, we need to determine if it’s preceded by a corresponding open parenthesis

If not, return false

But there is a problem here, which is that if the current parenthesis comparison is successful, how do we find the position of the corresponding character in the next parenthesis comparison

Here we can use the stack to maintain all the open parentheses, and when it comes to open parentheses, push it

When a close parenthesis is encountered, the top of the stack is the corresponding character. If the two characters are not the corresponding parenthesis, return false, otherwise the top of the stack is eject. This ensures that the top of the stack is still the corresponding character when the parenthesis is traversed

The solution is as follows:

  1. Create a stack to store all the left parentheses later
  2. Instead of having to code the judgment logic once for each closing bracket, create oneobjMaintain the correspondence between brackets
  3. Iterates through the string, pushing the current character if it is an open parenthesis
  4. If the current character is a close parenthesis, checks whether the element at the top of the stack is the corresponding open parenthesis, if not, returnsfalseOtherwise, the top element of the stack will be ejected for subsequent comparison
  5. If the string traverses smoothly, all closing parentheses have corresponding parentheses
  6. Check whether the stack is empty. If it is not empty, there are extra left parenthesesfalseOtherwise, the left and right parentheses completely correspond to each othertrue

The code is as follows:

Var isValid = function (s) {/ / create a stack storage left parenthesis const stack = [], / / using the obj maintain correspondence obj = {') ', '(','] ':' [', '} ':' {'} / / traversal string for (let I = 0; I < s.l ength; i++) {switch (s [I]) {/ / if the left parenthesis, stack case '(' : case' [' : case '{' : Stack. Push (s[I]) break; // If it is a close parenthesis, return false case ')': case ']': case '}': if(stack.length === 0 || stack.pop() ! == obj[s[i]]) return false; break; Return stack.length === 0}; return stack.length === 0; return stack.length === 0;Copy the code

At this point, we have leetcode-20- valid parentheses

If you have any questions or suggestions, please leave a comment!