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.

Link: leetcode-cn.com/problems/va…

Their thinking

For an unclosed open parenthesis, the further back the open parenthesis, the further forward the corresponding close parenthesis. Satisfy last in first out, use stack.

The problem solving steps

  • Create a new stack
  • Scan the string, encounter the left parenthesis on the stack, encounter and the top parenthesis type match the right parenthesis on the stack, the type does not match directly judged illegal
  • Finally empty stack is legal, otherwise illegal
* @param {string} s * @return {boolean} */ var isValid = function(s) { if(s.length % 2 === 1) return false; Const stack = [] for(let I =0; i<s.length; i++){ const c = s[i] if(c === '(' || c === '[' || c === '{'){ stack.push(c) }else { let t = stack[stack.length-1] if( (t  === "(" && c === ')') || (t === '[' && c === ']') || (t === '{' && c === '}') ) { stack.pop() } else { return false } }  } return stack.length === 0 };Copy the code

Time complexity and space complexity

Time complexity O(n) Space complexity O(n)

Optimize code with map

The left and right parentheses can be represented as key-value pairs as follows:

* @param {string} s * @return {boolean} */ var isValid = function(s) { if(s.length % 2 === 1) return false; const stack = [] const map = new Map() map.set("(",")") map.set("[","]") map.set("{","}") for(let i=0; i<s.length; i++){ const c = s[i] if(map.has(c)){ stack.push(c) }else { let t = stack[stack.length-1] if( map.get(t) === c ) { stack.pop() } else { return false } } } return stack.length === 0 };Copy the code

Time complexity and space complexity

Time complexity O(n) Space complexity O(n)