This is the 18th day of my participation in the More text Challenge. For more details, see more text Challenge

Valid parentheses (question number 20)

The title

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

A valid string must meet the following requirements:

  1. The opening parenthesis must be closed with a closing parenthesis of the same type.
  2. The opening brackets 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

link

Leetcode-cn.com/problems/va…

explain

This one. This is a classic garbage problem.

At first, I thought it was not necessary to follow the order, so I carried out a wave of operations, the result is that this problem does not support such a format, for example, ([)], which can also form two complete brackets, but the order is different.

([{}]{}) {} ([{}]{}) {} ([{}]{});

So it’s easy to do this, just do a stack, make an object, and determine the matching relationship between the parentheses:

obj = {
  ')': '(',
  ']': '[',
  '}': '{'
}
Copy the code

And then if it’s an open bracket, it’s pushed into the stack, and if it’s a close bracket, it matches the last element in the stack, and if it’s not a pair, it returns false, and if it’s a pair, it removes the last element from the stack.

Very simple operation, this is the author’s first thought of the answer, in fact, this kind of matching bracket topic can basically use the stack to operate, convenient and fast.

Your own answer (stack)

var isValid = function(s) {
  var stack = []
      obj = {
        ')': '(',
        ']': '[',
        '}': '{'
      }
  for (const symbol of s) {
    if (!obj[symbol]) {
      stack.push(symbol)
    } else {
      if (obj[symbol] !== stack.pop()) return false
    }
  }
  return stack.length === 0
};
Copy the code

The code uses the stack to match parentheses, as explained in the explanation.

Notice the last line of code, why not just return true? The reason is that even if all the matching is done, the result will still be a few separate parentheses, which is not a good use case.

Better answer (stack + pruning)

If the length of the string is odd, return false. If the length of the string is odd, return false.

This also avoids meaningless calculation, the official answer has such a judgment 👇 :

var isValid = function(s) {
  if (s.length % 2 === 1) return false
  var stack = []
      obj = {
        ')': '(',
        ']': '[',
        '}': '{'
      }
  for (const symbol of s) {
    if (!obj[symbol]) {
      stack.push(symbol)
    } else {
      if (obj[symbol] !== stack.pop()) return false
    }
  }
  return stack.length === 0
};
Copy the code

Better answers (re + recursion)

Strictly speaking, this method is not a better answer, as it does not have the same runtime or memory footprint as the previous two methods, but I find it interesting and put it here.

Take a look at the code 👇 :

var isValid = function(s) { while (s.includes('()') || s.includes('[]') || s.includes('{}')) { if (s.includes('()')) { s  = s.replace('()', '') } if (s.includes('[]')) { s = s.replace('[]', '') } if (s.includes('{}')) { s = s.replace('{}', '') } } return s.length === 0 };Copy the code

This method does not look a little violent, but also feel a little interesting.

Logic is very simple, if there are any matching parentheses, replace directly, so had been iterations, the iteration to string not paired parentheses, finally return to the length of the string, if the length of the length of 0, is proved to be qualified string, if not zero, proved that the string has a problem, return false.

Or you can directly remove the judgment inside the iteration, replace on the end of the matter, which tube so much, plus a little pruning 👇 :

var isValid = function(s) {
  if (s.length % 2 === 1) return false
  while (s.includes('()') || s.includes('[]') || s.includes('{}')) {
    s = s.replace('()', '')
    s = s.replace('[]', '')
    s = s.replace('{}', '')
  }
  return s.length === 0
};
Copy the code

The runtime increased slightly, from 5% to 15%, but the memory footprint remained unchanged at 5%.

This kind of answer is only to provide ideas, the real use of this method is likely to be sprayed half dead.




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)

Those who are interested can also check out my personal homepage 👇

Here is RZ