A, the title

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

Second, the train of thought

  • If you find a pair of keys that match a value, pop out the last number in the stack. If you find a pair of keys that match a value, pop out the last number in the stack. When the stack is empty, it is a valid string
  • This can be done with arrays and maps

Third, solution

3.1 Solution To iterate over the string, using the way of array and stack simulation to solve the problem

var isValid = function (s) {
    if(! s || s.length %2! = =0) return false

    let stackArr = []
    let keyArr = ['('.'{'.'[']
    let valueArr = [') '.'} '.'] ']

    for (let i = 0; i < s.length; i++) {
        if (stackArr.length === 0) {
            stackArr.push(s[i])
        } else {
            let lastAlpha = stackArr[stackArr.length - 1]      
            let index = valueArr.findIndex(v= > v === s[i])
            if (index === -1) {
                stackArr.push(s[i])
            } else {
                if (lastAlpha === keyArr[index]) {
                    stackArr.pop()
                } else {
                    stackArr.push(s[i])
                }
            }
        }
    }

    return stackArr.length === 0
};
Copy the code

3.2 Solution 2: Map code is less and more concise

var isValid2 = function (s) {
    if(! s || s.length %2! = =0) return false

    let stackArr = []
    let map = new Map([['('.') '], ['{'.'} '], ['['.'] ']])

    for (const ch of s) {
        if(map.has(ch)) {
            stackArr.push(ch)
        } else {
            if(map.get(stackArr[stackArr.length -1]) !== ch || stackArr.length === 0) {
                return false
            } else {
                stackArr.pop()
            }
        }
    }

    return stackArr.length === 0
};
Copy the code

Iv. Submission of results

  • Notice that it didn’t pass the first time, notice that this happens, “(){}}{“