LeetCode——有效的括号(括号匹配)
LeetCode——有效的括号(括号匹配)
题目描述:
给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: “()”
输出: true
示例 2:
输入: “()[]{}”
输出: true
示例 3:
输入: “(]”
输出: false
示例 4:
输入: “([)]”
输出: false
示例 5:
输入: “{[]}”
输出: true
解题思路:
这是经典的括号匹配问题,我们可以用栈解决。因为字符串只包括三种括号,所以如果该字符串满足括号匹配,那字符个数必为偶数,因此我们先判断字符的个数是否是偶数,如果个数是奇数,则括号不匹配,返回false。
接下来我们判断括号的左括号还是右括号,如果是左括号则入栈,如果是右括号,首先判断栈是否为空,如果栈此时为空,则一定没有与右括号匹配的左括号。如果栈不为空,则判断栈顶元素是否为和该右括号对应的左括号,如果是,则将这个左括号出栈,如果不匹配就说明匹配失败,括号不匹配,返回false。
最后遍历完所有元素后,判断栈最后是否为空,如果栈为空就说明所有的括号已匹配完,则返回true;如果有元素没有被匹配,则说明括号无法全部匹配,返回false。
solution代码:
package LeetCode.isValid;
import java.util.Stack;
/*
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
*/
public class isValidSolution {
public static boolean solution(String s){
if(s.length() % 2 == 1){
return false;
}
Stack stack = new Stack();
for (int i = 0; i < s.length(); i++) {
if(s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{'){
stack.push(s.charAt(i));
}
else{
if(stack.empty()){
return false;
}
else if(s.charAt(i) == ')' && stack.peek().equals('(')){
stack.pop();
}
else if(s.charAt(i) == ']' && stack.peek().equals('[')){
stack.pop();
}
else if(s.charAt(i) == '}' && stack.peek().equals('{')){
stack.pop();
}
else{
return false;
}
}
}
if(stack.empty()){
return true;
}else{
return false;
}
}
}
main函数代码:
package LeetCode.isValid;
import java.util.Scanner;
public class isValidMain {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.println("输入字符串:");
String s = scan.next();
if (isValidSolution.solution(s)){
System.out.println("括号匹配");
}else{
System.out.println("括号不匹配");
}
}
}
测试用例结果:
LeetCode测试结果:
本文地址:https://blog.csdn.net/weixin_45295612/article/details/107376216
上一篇: JAVA集合篇---详细
下一篇: 循环语句