This is the fourth day of my participation in Gwen Challenge

The topic of dry

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:

Input: s = "()[]{}" Output: trueCopy the code
Input: s = "([)]" Output: falseCopy the code

Solution: Stack properties

Actually we could start with the string traversal again, and at the same time of traverse, is left parenthesis if we meet, will it into the stack, then if the traversal is right parenthesis, makes the elements in the stack, if match, the remove stack elements, by analogy, if the traversal to right parenthesis in stack elements, You can simply return false, because this is the property of parentheses. After the last walk, check to see if our stack is empty. If it is, it meets our requirements. If it is not, return false

Note: we do not need to put the close parenthesis on the stack; the close parenthesis is just for comparison.

Code implementation:

Execution time: 76 ms, beating 95.12% of all JavaScript commits

Memory consumption: 39.3 MB, beating 25.41% of all JavaScript commits

/ * * *@param {string} s
 * @return {boolean}* /
var isValid = function (s) {
    // Iterate through the string so that each open parenthesis is at the top of the stack. When the close parenthesis is encountered, determine that it does not match the nearest top pair. If it matches, remove the top element
    let stack = [];
    for (let i = 0; i < s.length; i++) {
        if (s.charAt(i) === '[' || s.charAt(i) === '(' || s.charAt(i) === '{') {
            stack.push(s.charAt(i))
        } else {
            if (stack.length == 0) {
                return false
            }
            let lastcode = stack.length - 1
            if (s.charAt(i) === ') ' && stack[lastcode] === '(' || s.charAt(i) === '} ' && stack[lastcode] === '{' || s.charAt(i) === '] ' && stack[lastcode] === '[') {
                stack.pop()// Remove the top element if the match is successful
            }else{
                return false}}}return stack.length===0
}
Copy the code