有人向我提出了以下问题...
给定字符串“( { [ } ] )”中的 N 个不同的左大括号和右大括号,检查该字符串是否有匹配的大括号。如果大括号匹配则返回 true,否则返回 false。
这是我想出的答案......
function braceeql(braces){
var leftpar = 0;
var rightpar = 0;
var leftbrace = 0;
var rightbrace = 0;
var leftcurl = 0;
var rightcurl = 0;
for(var index = 0; index < braces.length; index++){
if(braces[index] == ')'){
leftpar += 1;
}else if(braces[index] == '('){
rightpar += 1;
}else if(braces[index] == '['){
leftbrace += 1;
}else if(braces[index] == ']'){
rightbrace += 1;
}else if(braces[index] == '{'){
leftcurl += 1;
}else if(braces[index] == '}'){
rightcurl += 1;
}
}
if(leftcurl == rightcurl && leftbrace == rightbrace && leftpar == rightpar){
console.log(true)
}else{
console.log(false)
}
}
这确实是一段很丰富的代码,但它确实有效。我看到关于其他人如何解决这个问题的不同意见,但我想知道有没有更好/更干净的方法来解决这个算法而不影响大O?
我非常愿意接受建议和其他看待这个问题的方法。
使用堆栈
以下解决方案的时间复杂度为O(n)
function isBalanced(str) {
const map = {
'(': ')',
'[': ']',
'{': '}',
};
const closing = Object.values(map);
const stack = [];
for (let char of str) {
if (map[char]) {
stack.push(char);
} else if (closing.includes(char) && char !== map[stack.pop()]) {
return false;
}
}
return !stack.length;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)