20.有效的括号

[shengxinjing]

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。

[chennailiang]

贴个刚写的菜鸟版。

var isValid = function(s) {
  const sign = {
    '{':'}',
    '[':']',
    '(':')'
  }
  const stack = []
  s.split('').forEach(ele=>{
    if(stack.length){
      if(sign[stack[stack.length - 1]] && sign[stack[stack.length - 1]] === ele){
        stack.pop()
      }else{
        stack.push(ele)
      }
    }else{
      stack.push(ele)
    }
  })
  return !stack.length
};

[chennailiang]

感觉这样写更优一些，但执行结果变慢了，不知道是不是用例问题。

var isValid = function(s) {
  // 排除奇数长度字符串
  if(s.length % 2 !== 0) return false
  const sign = {
    '{':'}',
    '[':']',
    '(':')'
  }
  const stack = []
  for(let i = 0; i < s.length; i++){
    // 栈中有结束符跳出循环
    if(stack.length && Object.values(sign).includes(stack[stack.length - 1])) break
    if(sign[stack[stack.length - 1]] && sign[stack[stack.length - 1]] === s[i]){
      stack.pop()
      continue
    }
    stack.push(s[i])
  }
  return !stack.length
};

[aniu2016]

const brackets = {
  '{': '}',
  '(': ')',
  '[': ']'
};
var isValid = function(s) {
  if (s.length % 2 !== 0) return false;
  let stack = [];
  for (let i = 0; i < s.length; i++) {
    const char = s[i];
    if (isLeft(char)) {
      stack.push(char);
    } else {
      let leftBracket = stack.pop();
      if (!leftBracket || getEndBracket(leftBracket) !== char) return false;
    }
  }
  if (stack.length) return false;
  else return true;
};

function isLeft(char) {
  return char in brackets;
}
function getEndBracket(char) {
  return brackets[char];
}

[isboyjc]

执行用时 :60 ms, 在所有 JavaScript 提交中击败了90.35%的用户 内存消耗 :33.6 MB, 在所有 JavaScript 提交中击败了93.81%的用户 实在没其他办法了，不知道用时最短的那些人怎么写的

var isValid = function(s) {
    let source = {"(":")","[":"]","{":"}"}
    let symbol = []
    for (let i = 0; i < s.length; i++) {
        if(s[i] in source){
            symbol.push(source[s[i]])
        }else{
            if(symbol.pop() != s[i]){
                return false
            }
        }
    }
    return !symbol.length
};

[chenbingweb]

/**

• @param {string} s

• @return {boolean} */ let objs={ '(':')', '{':'}', '[':']' } var isValid = function(s) { if(s=='') return true if(s.length<2) return false

  let arr =[]; let flag = true; let flagArr=[] for(let i=0;i<s.length;i++){ if(objs[s[i]]) { arr.push(s[i]); } else { let sign = objs[arr.pop()];

       if(sign==s[i])
       {
           flag=true;
  
       }
       else
       {
           flag=false;
  
       }
  
   }
   flagArr.push(flag)
  

  } if(arr.length) return false; return flagArr.every(item=>item==true) }; 执行用时 :68 ms

[whoelse666]

var isValid = function (s) { let arr = s.split(''); let arr2 = []; for (let v of arr) { if (v === '(' || v === '[' || v === '{') { arr2.push(v); } else if (v === ')' || v === ']' || (v === '}' && arr2.length > 0)) { let str = ''; switch (v) { case ')': str = '('; break; case ']': str = '['; break; case '}': str = '{'; break; } if (arr2.indexOf(str) > -1) { arr2.pop(v); } else { return false } } }

return !arr2.length;

};

isValid('(]');

[kaizige10]

const dict = { '}': '{', ']': '[', ')': '(' }
var isValid = function (s) {
    const stack = []
    for (let i = 0; i < s.length; i++) {
        const c = s.charAt(i);
        if (c === '{' || c === '[' || c === '(') {
            stack.push(c)
        } else if (stack.pop() !== dict[c]) {
            return false
        }
    }
    return stack.length === 0
};

最快是60ms

[geolcn]

var isValid = function (s) {     let stack = []     for (let i = 0; i < s.length; i++) {         let cur = s.charAt(i)         if (cur == "(") {             stack.push(")")         } else if (cur == "[") {             stack.push("]")         } else if (cur == "{") {             stack.push("}")         } else if (stack.pop() != cur) {             return false         }     }     if (stack.length == 0) {         return true     } else {         return false     } };

Accepted 76/76 cases passed (56 ms) Your runtime beats 96.56 % of javascript submissions Your memory usage beats 83.78 % of javascript submissions (33.7 MB)

[kouchao]

const k = {
    ')' : '(',
    '}' : '{',
    ']' : '['
}
var isValid = function(str) {
    const s = []
    let i = 0
    while(i < str.length) {
        if(str[i] === '(' || str[i] === '{' || str[i] === '['){
            s.push(str[i])
        } else {
            if(s.length === 0){
                return false
            }
            const t = s.pop()
            if(t != k[str[i]]){
                return false
            }
        }
        i++
    }

    return s.length === 0
};

执行用时 :68 ms, 在所有 JavaScript 提交中击败了60.80%的用户 内存消耗 :35.2 MB, 在所有 JavaScript 提交中击败了29.75%的用户

[TimCN]

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  // (){}[]
  const RIGHT = {
    ")": "(",
    "}": "{",
    "]": "[",
  }
  const LEFT = {
    "(": true,
    "{": true,
    "[": true
  }

  const arr = s.split("");
  const symbols = []
  let result = true;
  for (let i = 0; i < arr.length; i++) {
    if (LEFT[arr[i]]) {
      symbols.push(arr[i])
    } else if (RIGHT[arr[i]]) {
      // 出stack
      if (RIGHT[arr[i]] !== symbols.pop()) {
        result = false;
        break;
      }
    }
  }
  if (symbols.length > 0) {
    result = false
  }
  return result;

};

[flames519]

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    const stack = []
    // const open = new Map([["(",")"],["{","}"],["[","]"]])
    const map = {
        "(":")",
        "{":"}",
        "[":"]"
    }
    for (const val of s) {
        // if(open.has(val)){
        if(val in map){
            stack.push(val)
            continue
        }
        // if(open.get(stack[stack.length-1])!==val){
        if(map[stack.pop()]!==val){    
            return false
        } 
        // stack.pop()
    }
    return stack.length === 0
};

88ms 39M

[Reesejia]

判断除了大中小括号中间夹着 多种字符，是否匹配

var isValid = function(s) {
    let Stack = []
    const left = ['(','{','[']
    const right = [')','}',']']
    let obj = {
        ')' :'(',
       '}':'{',
        ']':'['
    }
  for(let i = 0;i < s.length;i++){
      const item = s[i]
      if(left.includes(item)){
          Stack.push(item)
      }
      if(right.includes(item)) {
        if(Stack.length === 0){
            return false
        } else {
            let s1 = Stack.pop()
            if(obj[item] !== s1){
                return false
            }
        }
      }
  }
  console.log('Stack1', Stack)
    return !Stack.length
};

const s2 = '{sdf[sdf]sdf}}sdf}3e4r{sdf{er43{er}sdf}'
const ret = isValid(s2)
console.log('ret', ret)

[Betty-study]

var isValid = function(s) { let st = [] // 存储配对符号字典 const flagMap = new Map([['(', ')'], ['{', '}'], ['[', ']']]) // 1.遇到'(|{|['压入栈 // 2.遇到')|}|]'， 判断栈头是否与当前符号一致，并出栈 for(let i=0; i<s.length; i++) { if(flagMap.has(s[i])) { st.push(s[i]) } else if(flagMap.get(st.pop()) != s[i]){ return false } } return st.length===0 };

[coveyz]

var isValid = function (s) {
	let map = {
		'(': -1,
		')': 1,
		'[': -2,
		']': 2,
		'{': -3,
		'}': 3,
	};
	let stack = [];
	for (let i = 0; i < s.length; i++) {
		if (map[s[i]] < 0) {
			stack.push(s[i]);
		} else {
			let last = stack.pop();
			if (map[last] + map[s[i]] != 0) return false;
		}
	}
	if (stack.length > 0) return false;
	return true;
};