This is the 20th day of my participation in the August Text Challenge.More challenges in August

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. 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 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 <= 104
  • sOnly by brackets'[] {} ()'composition

Their thinking

According to the passage, we can infer the following.

  1. Length of valid parenthesis string, must be even!
  2. The close parenthesis must be preceded by the corresponding open parenthesis to cancel!
  3. If the opening parenthesis is not preceded by the corresponding opening parenthesis, then the string must not be a valid parenthesis!

Graphical presentation

code

/ / solution
let isValid = function(s) {
    let stack = [], length = s.length;
    if(length % 2) return false;
    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; }}return! stack.length; };/ / solution 2
var isValid = function(s) {
    s = s.split(' ');
    let sl = s.length;
    if (sl % 2) return false;
    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); }}return! stack.length; };Copy the code

Other ideas

Solution a:

Find the innermost pair of parentheses, cancel them, and repeat the process. If there are characters that cannot be eliminated, the string is invalid.

var isValid = function (s) { while (s.length) { var temp = s; s = s.replace('()', ''); s = s.replace('[]', ''); s = s.replace('{}', ''); if (s == temp) return false } return true; };

Solution 2:

As soon as the solution ran out of speed and memory were unsatisfactory, I suspected that it was the problem of Replace, so I rewrote it with the same idea, but unexpectedly the performance was worse.

var isValid = function (s) { var map = { "(": ")", "[": "]", "{": "}" } while (s.length) { var left = s[0]; if (! (left in map)) return false; var i = 1; while (s[i] ! = map[left] && i < s.length) left = s[i++]; if (s[i] ! = map[left]) return false s = s.slice(0, i - 1) + s.slice(i + 1, s.length); } return true };

Solution 3:

Or another way to think about it, you can go through it and match it. Next time, the first close parenthesis encountered must match the last element in the array. Otherwise, it will be an invalid string. After matching, the element will be removed from the array. If the final array is empty, all parentheses are matched, and the string is valid.

var isValid = function (s) { var map = { "(": ")", "[": "]", "{": "}" } var leftArr = [] for (var ch of s){ if (ch in map) leftArr.push(ch); Else {// If (ch! = map[leftArr.pop()]) return false; } } return ! Leftarr. length // prevent all left parentheses};

The last

I dreamed of traveling with swords

Look at the prosperity of the world

Young heart always some frivolous

Just a man after all

No regrets I go my way

“Front-end brush” No.20