Given a string containing just the characters`'('`,`')'`,`'{'`,`'}'`,`'['`and`']'`, determine if the input string is valid. An input string is valid if: 1. Open brackets must be closed by the same type of brackets. 2. Open brackets must be closed in the correct order. Note that an empty string is also considered valid. **Example 1:** ~~~ Input: "()" Output: true ~~~ **Example 2:** ~~~ Input: "()[]{}" Output: true ~~~ **Example 3:** ~~~ Input: "(]" Output: false ~~~ **Example 4:** ~~~ Input: "([)]" Output: false ~~~ **Example 5:** ~~~ Input: "{[]}" Output: true ~~~ ``` /** * @param {string} s * @return {boolean} */ var isValid = function(s) { var sta = [],target={}; target['(']=')'; target['[']=']'; target['{']='}'; for(let i=0;i<s.length;i++){ if(!sta.length){ sta.push(s[i]) }else{ if(s[i] === target[sta[sta.length-1]]){ sta.pop() } else { sta.push(sta[i]) } } } return !sta.length; }; ``` ``` var isValid = function(s) { const stack = []; for (let i = 0; i < s.length; i++) { const char = s[i]; if (char === '(' || char === '[' || char === '{') stack.push(char); else { if (char === ')' && stack.pop() !== '(' || char === ']' && stack.pop() !== '[' || char === '}' && stack.pop() !== '{') return false; } } return stack.length === 0; }; ```