括号字符串是否有效
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
```
/**
* 给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
* 有效字符串需满足:
* 左括号必须用相同类型的右括号闭合。
* 左括号必须以正确的顺序闭合。
* 注意空字符串可被认为是有效字符串。
* <p>关键点在于<b>括号对应</b>, 所以需要提前保存括号, 这里使用键值对比较合适</p>
* @param s
* @return
*/
public static boolean checkValidString(String s) {
// 执行用时 :4 ms, 在所有 java 提交中击败了71.86%的用户
//内存消耗 :34.2 MB, 在所有 java 提交中击败了85.82%的用户
if(s == null || s .equals("")) {
return true;
}
// 保存括号对应关系
Map<Character, Character> map = new HashMap<>(3);
map.put('(',')');
map.put('{','}');
map.put('[',']');
// 左括号集合
Set<Character> keys = map.keySet();
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char temp = s.charAt(i);
if(i == 0 && !keys.contains(temp)) {
return false;
}
if(keys.contains(temp)) {
stack.push(temp);
} else {
if(temp != (stack.isEmpty() ? '#' : map.get(stack.pop()))) {
return false;
}
}
}
return stack.isEmpty();
// 没用过java的栈结构, 所以使用了LinkedList, 但是执行时间和空间都比较大
// 执行用时 :15 ms, 在所有 java 提交中击败了9.23%的用户
//内存消耗 :36.1 MB, 在所有 java 提交中击败了40.88%的用户
/* String[] strings = s.split("");
LinkedList<String> strList = new LinkedList<>();
for (int i = 0; i < strings.length; i++) {
if(keys.contains(strings[i])) {
strList.add(strings[i]);
} else {
if(i == 0 || (i != 0 && strList.size() == 0)) {
return false;
} else {
// 判断括号是否匹配
if(strings[i].equals(map.get(strList.getLast()))) {
strList.removeLast();
continue;
} else {
return false;
}
}
}
}
if(strList.size() == 0) {
return true;
}
return false;*/
}
/**
* 执行用时 :3 ms, 在所有 java 提交中击败了86.43%的用户
* 内存消耗 : 34.4 MB, 在所有 java 提交中击败了 84.17%的用户
* @param s
* @return
*/
public static boolean checkValidString1(String s) {
if(s == null || s .equals("")) {
return true;
}
// 保存括号对应关系
Map<Character, Character> map = new HashMap<>(3);
map.put(')','(');
map.put('}','{');
map.put(']','[');
// 左括号集合
Set<Character> keys = map.keySet();
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
Character temp = s.charAt(i);
if(keys.contains(temp)) {
Character element = stack.isEmpty() ? '#' : stack.pop();
if(!element.equals(map.get(temp))) {
return false;
}
} else {
stack.push(temp);
}
}
return stack.isEmpty();
}
public static void main(String[] args) {
/* String s1 = "{}[]()";
String s2 = "([{}])";
String s3 = "][(){}";
String s4 = "({(())}";*/
String s5 = "[])";
// true
/* System.out.println(checkValidString(s1));
// true
System.out.println(checkValidString(s2));
// false
System.out.println(checkValidString(s3));
// false
System.out.println(checkValidString(s4));*/
System.out.println(checkValidString(s5));
}
```