一、问题
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
注意：空字符串可被认为是有效字符串。
示例 1：
输入："()"
输出：true
示例 2：
输入："()[]{}"
输出：true
示例 3：
输入："(]"
输出：false
示例 4：
输入："([)]"
输出：false
示例 5：
输入："{[]}"
输出：true
二、理解
验证括号的对称性，括号总共分为三类：小括号、中括号和大括号，可以利用栈先进后出的特性，将所有左括号【“(”、“[”、“{”】先入栈，然后再碰到右括号时，让它与栈顶的元素进行匹配，比如当遇到“)”时，如果栈顶是“(”，则说明匹配成功，栈顶元素出栈再继续字符串循环的流程，如果匹配错误就直接返回 false。假设要匹配字符串“(([]))”是否合法，执行流程如下：
首先遇到左括号，先入栈：
接下来又是左括号，继续入栈：
然后又是左括号，继续入栈：
接下来是右括号，与栈顶元素匹配，“[]”为一对合法的括号，匹配成功栈顶元素出栈：
接下来又是右括号，与栈顶元素匹配，“()”为一对合法的括号，匹配成功栈顶元素出栈：
接下来又是右括号，与栈顶元素匹配，“()”为一对合法的括号，匹配成功栈顶元素出栈：
当字符串循环结束并且栈为空栈时，则证明此字符串的括号匹配合法，最终的效果如下图所示：
三、解答
测试主类：
public static void main(String[] args) {
String s = "()";
Test test = new Test();
System.out.println(test.isValid(s));
}
1️⃣判断括号的有效性可以使用栈这一数据结构来解决。
遍历给定的字符串 ss，当遇到一个左括号时，期望在后续的遍历中，有一个相同类型的右括号将其闭合。由于后遇到的左括号要先闭合，因此可以将这个左括号放入栈顶。
当遇到一个右括号时，需要将一个相同类型的左括号闭合。此时，可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型，或者栈中并没有左括号，那么字符串 ss 无效，返回 false。为了快速判断括号的类型，可以使用哈希映射(HashMap)存储每一种括号。哈希映射的键为右括号，值为相同类型的左括号。
在遍历结束后，如果栈中没有左括号，说明字符串 ss 中的所有左括号完成闭合，返回 true，否则返回 false。
注意到有效字符串的长度一定为偶数，因此如果字符串的长度为奇数，可以直接返回 false，省去后续的遍历判断过程。
public boolean isValid(String s) {
int n = s.length();//括号的长度
if (n % 2 == 1) {//括号不是成对的直接返回 false
return false;
}
//把所有对比的括号存入 map，对比时用
Map<Character, Character> pairs = new HashMap<Character, Character>() {{
put(')', '(');
put(']', '[');
put('}', '{');
}};
//定义栈，用于存取括号（辅助比较）
Deque<Character> stack = new LinkedList<Character>();
//循环所有字符
for (int i = 0; i < n; i++) {
char ch = s.charAt(i);
//为右边的括号，如 ')'、'}' 等
if (pairs.containsKey(ch)) {
//栈为空或括号不匹配
if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
return false;
}
//是一对括号，执行出栈（消除左右括号
stack.pop();
} else {
//左边括号，直接入栈
stack.push(ch);
}
}
return stack.isEmpty();
}
2️⃣解题思路：
- 特判：过滤空字符串。
- 创建一个辅助栈。
- 遍历，对每一个字符进行如下操作：
①若为左括号，则往栈中存放右括号。
②若为右括号，如果栈为空或者该右括号与取出的栈顶元素不一样，则返回 false。 - 返回栈是否为空的状态。
public boolean isValid(String s) {
//1.特判
if (s.isEmpty()) return true;
//2.创建辅助栈
Stack<Character> stack = new Stack<>();
//3.遍历
for (char c : s.toCharArray()) {
if (c == '(') {
stack.push(')');
} else if (c == '[') {
stack.push(']');
} else if (c == '{') {
stack.push('}');
} else if (stack.isEmpty() || c != stack.pop()) {
return false;
}
}
//4.返回
return stack.isEmpty();
}
3️⃣可以使用借助 Java 中的 replace 方法来实现，循环的消除字符串中的括号，比如将“()”或“[]”或“{}”循环得替换为空，最后在执行完成之后如果字符串为空，则说明字符串中的括号是合法的，具体实现代码如下：
public boolean isValid(String s) {
int len;
do {
len = s.length();
//消除成双成对的符号
s = s.replace("()", "").replace("[]", "").
replace("{}", "");
} while (len != s.length()); //不能再进行替换了，replace没有替换任何字符
return s.length() == 0;
}
网友评论