This is the 14th day of my participation in the August More Text Challenge. For details, see: August More Text Challenge

preface

As a developer, and the development of our daily format should be used in the process of calibration tools, such as I am using ESLint, it can help us to check the writing format is correct, are such as less commas, semicolons, fewer or less wrote brackets, it is how to identify less wrote enclosed, I don’t know. Just another algorithm problem is to determine whether valid parentheses, we might as well have a look

Topic describes

Given a only include a ‘(‘,’) ‘, ‘{‘,’} ‘, ‘/’, ‘ ‘the string s, determine whether a string is effective.

A valid string must meet the following requirements:

The opening parenthesis must be closed with a closing parenthesis of the same type. The opening brackets 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,

Their thinking

  • First of all, we find that the brackets that meet the conditions are the three cases ()[]{}, so we only need to judge whether the input items meet the three conditions
  • We declare an array calculateArr, where we store the open parentheses, and use a for loop to determine if each item is an open parenthesis, and if it is, we store it in calculateArr
  • If it’s not an open parenthesis, compare this item to calculatearr.pop (), continue if it’s a pair of parentheses, and return false if it’s not
  • To determine whether the calculateArr is empty, return true if the calculateArr is empty, otherwise return false. There are two methods. The code is as follows

Method 1:

var isValid = function(s) {
    let originalArr= s.split(' ')
    let calculateArr=[]
    let count=0
    for(let i=0; i<originalArr.length; i++){if(originalArr[i]==='(' || originalArr[i]==='[' ||originalArr[i]==='{'){
            calculateArr.push(originalArr[i])
            count++
        }else if(originalArr[i]===') ' && calculateArr[count-1= = ='('  || originalArr[i]==='] ' && calculateArr[count-1= = ='[' ||originalArr[i]==='} '&& calculateArr[count-1= = ='{'){
            calculateArr.pop(originalArr[count-1])
            count--

        }else{
            return false}}if(calculateArr.length){
        return false
    }else{
        return true}};Copy the code

The running result of LeetCode is as follows:

Method 2:

var isValid = function(s) {
    let templete = new Map()
    templete.set("(".")")
    templete.set("["."]")
    templete.set("{"."}")
    let calculate=[]
    for(let i=0; i<s.length; i++){if(templete.has(s[i])){
            calculate.push(templete.get(s[i]))
        }else{
            if(calculate.pop()! ==s[i]){return false}}}if(calculate.length){
        return false
    }else{
        return true}};Copy the code

The running result of LeetCode is as follows:

conclusion

Although the above two methods are different, but the idea is the same, is to clarify the three states of parentheses, and then the input of the content of a comparison, finally get the result, the second method looks a little more concise, but also more efficient, if there is a better method, welcome to comment.