题目：给定一个只包含大、中、小括号的字符串，判断字符串是否有效。也就是同一种括号的左右部分需要对应。
例如：
()–合法
[]–合法
[()]–合法
{()}–合法
[(])–不合法
[)]–不合法
实现思路：左括号默认就合法，需要再检查是否有匹配的右括号。
左括号–》压入堆栈右括号–》同栈顶元素进行匹配检查，匹配则栈顶元素pop，不匹配说明该字符串不合法如果能匹配上，堆栈必然是空的。
时间复杂度O(n)
空间复杂度O(n)
代码如下：
package com.example.demo;
import java.util.Stack;
public class ValidString {
public static void main(String[] args) {
char[] chars_1 = {'(',')'};//合法
char[] chars_2 = {'(',')','[',']'};//合法
char[] chars_3 = {'(',')','[',']','[','}'};//不合法
System.out.println(valid(chars_1));
System.out.println(valid(chars_2));
System.out.println(valid(chars_3));
}
public static boolean valid(char[] chars) {
Stack<Character> stack=new Stack<>();
for(char c: chars) {
if(c == '(') {
stack.push(c);
} else if(c == '[') {
stack.push(c);
} else if(c == '{') {
stack.push(c);
} else if(c == ')') {
if(stack.empty()) {
return false;
}
Character peek = stack.peek();
if(peek == '(') {
stack.pop();
} else {
return false;
}
} else if(c == ']') {
if(stack.empty()) {
return false;
}
Character peek = stack.peek();
if(peek == '[') {
stack.pop();
} else {
return false;
}
} else if(c == '}') {
if(stack.empty()) {
return false;
}
Character peek = stack.peek();
if(peek == '{') {
stack.pop();
} else {
return false;
}
}
}
if(!stack.empty()) {
return false;
}
return true;
}
}结果：
true
true
false上面的代码看起来比较冗余，不够简洁，还有一种思路，能够让代码简洁。思路就是将括号放入map，根据每次的括号，来判断是左括号就压入栈，右括号就判断与前一个字符是否对称。
代码如下：
package com.example.demo;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
public class ValidString2 {
public static void main(String[] args) {
char[] chars_1 = {'(',')'};//合法
char[] chars_2 = {'(',')','[',']'};//合法
char[] chars_3 = {'(',')','[',']','[','}'};//不合法
System.out.println(valid(chars_1));
System.out.println(valid(chars_2));
System.out.println(valid(chars_3));
}
public static boolean valid(char[] chars) {
Map<Character,Character> mapChar = new HashMap<>();
mapChar.put(')','(');
mapChar.put(']','[');
mapChar.put('}','{');
Stack<Character> stack=new Stack<>();
for(char c :chars) {
if(!mapChar.containsKey(c)) {
//不在map的key中说明是左括号，要放入stack中
stack.push(c);
} else {
//在map的key中，说明是右括号，要判断是否合法
if(stack.empty()) {
return false;
}
Character peek = stack.peek();
if(peek == mapChar.get(c)) {
stack.pop();
} else {
return false;
}
}
}
if(!stack.empty()) {
return false;
}
return true;
}
}结果：
true
true
false第二种实现比第一种实现的valid方法，精简了很多，思路也并不复杂。