Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

I. Title Description:

Determines whether the parentheses match the string

  • A string s may contain {} () [] parentheses
  • Check if s matches the parentheses
  • If (a{b}c) matches, {a(b or {a(b)c) does not match

Ii. Analysis of Ideas:

Data structure: stack

  • After the advanced
  • API: Push Pop Length
  • Related: queue, heap

  • Stack VS array
  • The stack, the logical structure, is a theoretical model, no matter how implemented, not constrained by any language. Right
  • Array, physical structure, real functionality implementation, limited by programming language

Stacks and arrays are two different things, arrays implement stacks, linked lists implement stacks

Train of thought

  1. Press the left parenthesis {([
  2. Close parenthesis})] is used to determine the top of the stack
  3. Finally, check whether length is 0
/ * * *@description Bracket matching *@author Have a way to * /

 /** * Checks whether the parentheses match *@param str str
  */
 
 / * * * *@param Left Left parenthesis *@param Right close parenthesis */
function isMatch(left:string,right:string) :boolean{
    if(left === '{' && right === '} ') return true
    if(left === '(' && right === ') ') return true
    if(left === '[' && right === '] ') return true

}




 function matchBracket(str:string) :boolean{
     const length = str.length
     if(length===0) return true

     const stack = []

     const leftSymbols = '{(['
     const rightSymbols = '})] '


     for(let i=0; i < length; i++){const s = str[i]

         if(leftSymbols.includes(s)){
             // Open parenthesis, press the stack
             stack.push(s)
         }else if(rightSymbols.includes(s)){
             // Close parentheses to determine the top of the stack
             const top = stack[stack.length-1]
             if(isMatch(top,s)){
                 stack.pop()
             }else{
                 return false}}}return stack.length === 0

 }


 // Function test
 const str = 'abc{}(asdasd)'
 console.info(matchBracket(str))
Copy the code