I. Title Description:

The original address

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.

Tip:

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

Ii. Analysis of Ideas:

In fact, the typical stack thinking.

  • It’s only parentheses, so it’s only STR that has an odd length is definitely not valid
  • Traversal string
  • When it hits an open parenthesis, it pushes it into another array
  • If I see a close bracket, I’m going to see if it’s the last item in the array and if I see a close bracket, I’m going to throw the last item out of the array
  • If there is a string in the array, it is invalid. If there is a string in the array, it is invalid

A slightly more subtle twist of js: the map type maps open parentheses to close parentheses

Iii. AC Code:

/ * * *@param {string}
 * @return {boolean}* /

const isValid = function (s) {
  if (s.length % 2= = =1) {
    return false;
  }
  const res = [];
  const map = new Map([['['.'] '],
    ['('.') '],
    ['{'.'} ']]);for (const str of s) {
    const isLeft = map.has(str);
    if(isLeft || ! res.length) res.push(str);else {
      // if it is the right symbol, see if it is the right parenthesis corresponding to the last open parenthesis of the res
      If yes, delete the last one; if no, return false
      if (map.get(res[res.length - 1]) !== str) {
        return false; } res.pop(); }}return! res.length; };Copy the code

Iv. Summary:

  • The application of stack idea
  • Use of map types