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.

Answer:

Use the idea of a stack, first in, then out. JavaScript doesn’t have stacks, but arrays can be used as stacks.

Therefore, you can iterate through a number array, encountering an open parenthesis to the stack (new array to store), and a close parenthesis to match the top of the stack. If the type matches, take it off the stack and compare the next close bracket to the top element. Until the new array element is empty or does not match false.

annotation

  1. Check whether the array is empty or odd, and if so, print false.
  2. Iterate through the array, pushing if an open parenthesis is encountered. When a close parenthesis is encountered, it matches the top of the stack first, and if the type matches, it is removed from the stack. If not, the value is false.
  3. Check whether the stack is empty.
var isValid = function(s) {
  // 1. Check whether the array is empty or odd. If yes, print false.
  const length = s.length
  if(! s || length %2= = =1) {
    return false
  }
  // 2. Iterate over the number group, if it encounters an open parenthesis, push (push). When a close parenthesis is encountered, it matches the top of the stack first, and if the type matches, it is removed from the stack. If not, the value is false.
  const stack = []
  for ( let i = 0; i < length; i += 1) {
    const c = s[i]
    if (c === '(' || c === '{' || c === '[') {
      stack.push(c)
    } else {
        const t = stack[stack.length - 1]
        if(
          (t === '(' && c === ') ') || 
          (t === '{' && c === '} ') || 
          (t === '[' && c === '] ')
        ) {
          stack.pop()
        } else {
          return false}}}// 3. Check whether the stack is empty.
  return stack.length === 0 ? true : false
};
Copy the code

Improvement and Thinking

Step 1

1. Check whether the array is empty

if (s === [] || length % 2 === 1)
Copy the code

After, also write

if (! s || length % 2 === 1)Copy the code

Note:

  • You should check whether the stack is empty before fetching the top element

  • Consider the case where the input is “] “. The value of index -1 is taken. Undefined in JS, but error may be reported in other languages

Step 2

“2. Iterate through the array and push if an open parenthesis is encountered. When a close parenthesis is encountered, it matches the top of the stack first, and if the type matches, it unmatches the stack.

This step can also be done using the Switch/case method or the Map method.

The specific operation steps are as follows:

Switch/case method

for(let item of s){
        switch(item){
            case "{":
            case "[":
            case "(":
                stack.push(item);
                break;
            case "}":
                if(stack.pop() ! = ="{") return false;
                break;
            case "]":
                if(stack.pop() ! = ="[") return false;
                break;
            case ")":
                if(stack.pop() ! = ="(") return false;
                break; }}Copy the code

Map methods (involving algorithms – dictionaries)

let map = new Map([[') '.'('], ['] '.'['], ['} '.'{']]);
    let stack = [];
    for(let i of s){
        if (map.get(i)) {
            if (stack[stack.length - 1] !== map.get(i)) return false;
            else stack.pop();
        } else{ stack.push(i); }}Copy the code

Step 3: Judge

3. Check whether the stack is empty

if (stack.length === 0) { return true }
Copy the code

After, can also write

return stack.length === 0
Copy the code

It can also be written as a ternary expression

return stack.length === 0 ? true : false
Copy the code