This article is participating in the nuggets team number online activity, click to see the dachang spring recruiting positions

I. Title Description:

Leetcode 20. Valid parentheses

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.

 

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
  • S is in parentheses only'[] {} ()'composition

Ii. Analysis of Ideas:

  • As prompted, the parenthesis type can be enumerated, and s consists only of parentheses'[] {} ()'Composition;
  • They want valid parentheses to be closed left and right, in the correct order;
  • According to the stack properties of the array, utilizepushandpopTo push and push;
  • If the last stack is empty, it indicates that the left and right are closed and the order is correct.

AC code

/** * @param {string} s * @return {boolean} */ var isValid = function(s) { let start = { '(': 1, '[': 2, '{': 3 }; let end = { ')': 1, ']': 2, '}': 3 }; let arr = []; for (var i = 0; i < s.length; i++) { if (end[s[i]] && (end[s[i]] == arr[arr.length - 1])) { arr.pop(end[s[i]]); } else { if (start[s[i]]) { arr.push(start[s[i]]); } else { return false; } } } if (arr.length == 0) { return true; } else { return false; }};Copy the code

The execution result

Execution result: Passed execution time: 80 ms, beat 85.99% of users in all JavaScript commits memory consumption: 37.8 MB, beat 83.74% of users in all JavaScript commitsCopy the code

Iv. Summary:

  • The stack can be understood as a bottle, in the stack is put into the bottle, out of the stack is taken out of the bottle;
  • The bottle has only one opening for entering and leaving the stack;
  • So all the exits are from the top of the stack, so last in, first out;