有效括号，解决 Facebook 面试题。
这是最常见的筛选问题之一，尤其是在 HackerRank 进行面试时，他们很可能会问到这个问题。我被 HackerRank 问了四次同样的问题。
问题：给定一个仅包含字符'(', ')', '{', '}', '['和']'的字符串，判断该输入字符串是否有效。
输入字符串有效需满足以下条件：
左括号必须用同类型的括号闭合；
左括号必须按正确的顺序闭合；
空字符串也被视为有效。
例如：
string = "()[]{}" //valid
string = "[{()]}" //invalid
string = "" //valid
我们来解决这个问题。
最基本的，这个问题要求我们找到匹配的左括号和右括号。所以对于以下情况：
`(", ")` 是有效的右括号
，`{", "}` 是有效的右括号
，`"[", "]` 是有效的右括号。
换句话说，我们可以说这些“对”相互抵消，由此我们可以说顺序很重要。
一个好的数据结构可以帮助我们：
1 > 存储括号并在找到匹配项时取消它们；
2 > 跟踪括号。
是栈。我们将左括号压入栈中，遇到右括号时将其弹出，同时我们还可以检查弹出的右括号是否与左括号匹配。
实施 - 1
这里我们可以做一个小优化，检查字符串长度是否为偶数。如果不是偶数，显然该字符串无效。
将上述想法转化为代码：
var isValid = function(S) {
let stack = [];
if(S == '') return true;
if(S%2 != 0) return false;
for(let s of S){
if(s == '(' || s == '{' || s == '['){
stack.push(s);
}else{
if(stack.length == 0) return false;
let c = stack.pop();
if(c == '(' && s != ')'){
return false;
}
if(c == '{' && s != '}'){
return false;
}
if(c == '[' && s != ']'){
return false;
}
}
}
if(stack.length != 0) return false; // for conditions like "{([])}}}"
return true;
};
现在这样运行良好，但我们还能做得更好吗？仅仅为了检查“配对”，就用了太多 if-else 条件语句。让我们尝试让它更简洁一些。
实施方案 - 2
由于if条件的主要工作是匹配括号，我们使用另一种数据结构，即哈希映射。
由于右括号必须与对应的左括号匹配，因此我们建立了右括号和左括号之间的映射关系。
该算法的工作原理如下：
1 > 检查当前符号是否在哈希表中，如果不在，则将其压入栈中。2
> 如果当前符号在哈希表中，则从栈中弹出并将其与哈希表中对应条目的值进行比较。
因此，如果当前符号的顶部是“)”，则我们从栈中弹出该符号，并将弹出的值与哈希映射中与“)”对应的值“(”进行比较，如果它们不相同，则该字符串无效。
代码会解释得很清楚。
var isValid = function(S) {
if(S == '') return true;
if(S.length%2 != 0) return false;
let map = {};
map[")"] = "(";
map["}"] = "{";
map["]"] = "[";
console.log(map);
let stack = [];
for(let s of S){
if(!map[s]){
stack.push(s);
}else{
if(stack.length == 0) return false;
let c = stack.pop();
if(c != map[s]) return false;
}
}
if(stack.length !=0) return false;
return true;
};
希望我的解释对您有所帮助。如果您有更好的解决方法，请与我们分享 :)
github：https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/ValidParentheses.js
文章来源：https://dev.to/akhilpokle/valid-parentheses-solving-a-facebook-interview-question-410o