Topic describes

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: true Example 2:

Input: s = “()[]{}” Output: true Example 3:

Input: s = “(]” Output: false Example 4:

Input: s = “([)]” Output: false Example 5:

Input: s = “{[]}” Output: true

Tip:

1 <= s.length <= 10410^4104 s consists only of parentheses ‘()[]{}’

Source: LeetCode link: leetcode-cn.com/problems/va… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Antithesis thought

  1. In addition to being of the same type, the left and right parentheses should also match the proximity principle, such as “(“, when encountered the first “)” should match the last “(“, which conforms to the stack operation, last in, first out.
  2. When we encounter an open parenthesis, we push it onto the stack to be matched.
  3. When a close parenthesis is encountered, it goes to the top of the stack to find whether it is an open parenthesis that can be paired. If the pair succeeds, it removes the element at the top of the stack and waits for the next open parenthesis to be paired.

Answer key code

* @lc app=leetcode.cn id=20 lang=javascript ** [20] valid parentheses */ // @lc code=start /** * @param {string} s * @return {boolean} */ var isValid = function(s) { const n = s.length; if (n % 2 === 1) { return false; } const stack = []; const map = new Map([ [")","("], ["}","{"], ["]","["] ]); For (let si of s) {if (map.has(si)) {if (map.has(si)) {if (! stack.length || stack[stack.length - 1] ! == map.get(si)) { return false } stack.pop(); }else{stack.push(si)//si is left parenthesis when pushed to the top of the stack to wait for pairing}} return! stack.length; // if the stack is empty, all the open brackets are matched successfully}; // @lc code=endCopy the code