Leetcode Stack

20 有效的括号

/// 97.08%  68.03%
var isValid = function(s) {
	let stack = [];
	for(i of s){
		if (i === '(' || i === '{' || i === '['){
			stack.push(i)
		}else{
			if (stack.length > 0){
				let top = stack.pop()
				if (!top) return false
				if ((top === '(' && i === ')') || (top === '[' && i === ']') || (top === '{' && i === '}')){
					
				}else{
					return false
				}
			}else{
				return false
			}
		}
	}
	return stack.length === 0
};

因为每个元素都会且仅会进入栈一次，每次时间复杂度是O(1)，因此总的时间复杂度是O(n)。空间复杂度也是O(n)。还有一个结果让人疑惑的解法。

/// 99.85%   63.52%
var isValid = function(s) {
	let stack = [];
	let m = new Map()
	m.set(')', '(')
	m.set(']', '[')
	m.set('}', '{')
	for(i of s){
		if (!m.has(i)){
			stack.push(i)
		}else{
			if (stack.length > 0 && stack.pop() === m.get(i)){
				
			}else{
				return false
			}
		}
	}
	return stack.length === 0
};

这个让我疑惑的地方在于多使用了一个Map而且主要改动的代码也只是括号的配对的那个if语句，居然速度快了足足8ms。