1. Title Description

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 <= 10^4
  • S consists only of parentheses ‘()[]{}’

Second, train of thought analysis

"()" "() [] {}" "{[]}"Copy the code

Look at the inputs in a given example of a valid string and process them in order that at one point they are all symmetric.

According to the last in, first out (LIFO) principle of the stack, the order of loading and unloading of a set of data is exactly symmetric.

So we can use the stack to push characters one by one, and when we find a matching pair we push them off the stack.

Of course, the operation of pushing and removing the close parenthesis on the stack can be omitted. When the close parenthesis matches the character at the top of the stack, the open parenthesis at the top of the stack can be directly pushed off the stack.

Pushing each pair of brackets off the stack ensures that the top bracket is always the next left bracket that needs to be matched.

Finally, if all strings match, the stack must be empty. If the stack is not empty, the input is not a valid string.

AC code

/** * @param {string} s * @return {Boolean} */ const isValid = function(s) {// Use a map to maintain the mapping between open parentheses and close parentheses, which is easy to compare const map = {" (": ")", "[": "]", "{": "}"}; // An empty string returns true if (! s) { return true; } // Use a stack to hold open parenthesis const stack = []; For (let I = 0; i < s.length; i++) { const ch = s[i]; If (["(", "{","["].indexof (ch)! Else {// If the stack is not empty and the left parenthesis at the top of the stack does not match the current character, return false if (! Stack. The length | | map [stack. Pop ()]! = = ch) {return false;}}} / / if the stack is empty then return all matching! Stack. Length;};Copy the code

Four,

When encountering symmetry problems, you can try to solve the problem by starting with the stack.

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign