20.有效的括号
问题类型：Easy
给定一个仅包含字符'(', ')', '{', '}', '[' and ']',的字符串s确定输入字符串是否有效。
一个输入字符串是有效的，如果：
- 开放式括号必须通过相同类型的支架关闭。
- 必须按正确的顺序关闭开放括号。
- 每个关闭支架都有相同类型的相应开放式。
示例1：
输入：
"()"
输出：
true
示例2：
输入：
"()[]{}"
输出：
true
示例3：
输入：
"(]"
输出：
false
约束：
1 <= s.length <= 104
s consists of parentheses only '()[]{}'.
方法：
为了解决此问题，我们可以使用stack数据结构。这个想法是通过字符通过输入字符串character和：
-
如果我们遇到开口支架（'（'，'{'，'['），我们将其推到堆栈上。
-
如果我们遇到闭合括号（'），'}'，']'），我们检查堆栈是否为空。如果是这样，我们返回false，因为没有相应的打开括号可以匹配当前关闭括号。
-
如果堆栈不是空的，我们会从堆栈中弹出顶部元素，并检查它是否匹配当前关闭支架。如果它们不匹配，我们会返回false，因为支架不是正确的顺序。
-
处理所有字符后，如果堆栈中剩下任何元素，则意味着有无与伦比的打开括号，因此我们返回false。
-
如果处理所有字符后堆栈是空的，我们返回true，表明输入字符串有效。
-
这种方法可确保按正确的顺序关闭开放式括号，并且还处理输入字符串仅包含打开括号或仅关闭支架的情况。
代码：
class Solution {
public boolean isValid(String s) {
// using stack
Stack<Character> stack = new Stack<>();
for(char ch: s.toCharArray()){
switch(ch){
case '(':
case '{':
case '[':
stack.push(ch);
break;
case ')':
if(stack.isEmpty() || stack.pop() != '('){
return false;
}
break;
case'}':
if(stack.isEmpty() || stack.pop() != '{'){
return false;
}
break;
case ']':
if(stack.isEmpty() || stack.pop() != '['){
return false;
}
break;
}
}
return stack.isEmpty();
}
}
为什么这种方法？
-
基于堆栈的方法可确保打开括号与相应的闭合括号匹配，并保持正确的顺序。
-
它有效地使用无与伦比的支架处理边缘案例，并允许早日检测到无效的字符串。
-
这种方法的简单性和线性时间复杂性使其成为确定给定字符串中括号的有效性的最佳解决方案。
愉快的编码，
湿婆