给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([)]"
输出：false
示例 5：
输入：s = "{[]}"
输出：true
提示：
1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
package cn.fansunion.leecode.collection;
import java.util.Stack;
/**
* 20. 有效的括号 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
*
* 有效字符串需满足：
*
* 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。
*
* 来源：力扣（LeetCode） 链接：力扣 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*
* @author [email protected]
*
* 2022-2-18
*/
public class ValidParentheses {
/* 示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([)]"
输出：false
示例 5：
输入：s = "{[]}"
输出：true*/
/**
* 遍历字符串中的字符，遇到左括号，放到stack；遇到右括号，和栈顶的元素进行配对；如果匹配，移除栈顶，再遍历下一个；否则，返回false
* todo：优化点，维护一个map：右括号为key，左括号为value
* @param s
* @return
*/
public boolean isValid(String s) {
if (s == null || s.length() % 2 == 1) {
return false;
}
Stack<Character> stack = new Stack<>();
for (int index = 0; index < s.length(); index++) {
char ch = s.charAt(index);
if (ch == '(' || ch == '[' || ch == '{') {
stack.add(ch);
} else if (ch == ')') {
if(stack.isEmpty()) {
return false;
}
Character top = stack.peek();
//遍历中匹配了
if (top != null && top.equals('(')) {
stack.pop();
} else {
return false;
}
} else if (ch == ']') {
if(stack.isEmpty()) {
return false;
}
Character top = stack.peek();
//遍历中匹配了
if (top != null && top.equals('[')) {
stack.pop();
} else {
return false;
}
} else if (ch == '}') {
if(stack.isEmpty()) {
return false;
}
Character top = stack.peek();
//遍历中匹配了
if (top != null && top.equals('{')) {
stack.pop();
} else {
return false;
}
} else {
throw new IllegalArgumentException("param valid");
}
}
//全部成对匹配的情况，是：入栈和出栈了，剩余元素为0
return stack.size()==0;
}
/**
* 遍历字符串中的字符，遇到左括号，放到stack；遇到右括号，和栈顶的元素进行配对；如果匹配，移除栈顶，再遍历下一个；否则，返回false
* 问题点：用例不够全，自测不到位，"){"，右括号开头的或者奇数位是右括号的
* @param s
* @return
*/
public boolean isValidError(String s) {
if (s == null || s.length() % 2 == 1) {
return false;
}
Stack<Character> stack = new Stack<>();
for (int index = 0; index < s.length(); index++) {
char ch = s.charAt(index);
if (ch == '(' || ch == '[' || ch == '{') {
stack.add(ch);
} else if (ch == ')') {
Character top = stack.peek();
//遍历中匹配了
if (top != null && top.equals('(')) {
stack.pop();
} else {
return false;
}
} else if (ch == ']') {
Character top = stack.peek();
//遍历中匹配了
if (top != null && top.equals('[')) {
stack.pop();
} else {
return false;
}
} else if (ch == '}') {
Character top = stack.peek();
//遍历中匹配了
if (top != null && top.equals('{')) {
stack.pop();
} else {
return false;
}
} else {
throw new IllegalArgumentException("param valid");
}
}
//全部成对匹配的情况，是：入栈和出栈了，剩余元素为0
return stack.size()==0;
}
}
package test.leecode.collection;标签：false,括号,3619,top,Assert,有效,isValid,test,stack From： https://blog.51cto.com/fansunion/6056782
import org.junit.Assert;
import org.junit.Test;
import cn.fansunion.leecode.collection.ValidParentheses;
/**
* @author [email protected]
*
* 2022-2-25
*/
public class ValidParenthesesTest {
@Test
public void test() {
ValidParentheses test = new ValidParentheses();
Assert.assertFalse(test.isValid("){"));
//true
Assert.assertTrue(test.isValid("()"));
Assert.assertTrue(test.isValid("[]"));
Assert.assertTrue(test.isValid("{}"));
Assert.assertTrue(test.isValid("()[]{}"));
Assert.assertTrue(test.isValid("{[]}"));
Assert.assertTrue(test.isValid("(())"));
Assert.assertTrue(test.isValid("[[]]"));
Assert.assertTrue(test.isValid("[[]]()"));
Assert.assertTrue(test.isValid("[[]]{}"));
Assert.assertTrue(test.isValid("[[]]{}"));
//false
Assert.assertFalse(test.isValid("(]"));
Assert.assertFalse(test.isValid("([)]"));
Assert.assertFalse(test.isValid("(((]]"));
Assert.assertFalse(test.isValid("([[}"));
//true
Assert.assertTrue(test.isValid(""));
}
}