leetcode - 括号字符串是否有效
程序员文章站
2023-10-28 19:43:52
括号字符串是否有效 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。 / 给定一个只包括 '('，')'，'{'，'}'，'['，' ......
括号字符串是否有效
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
```
/**
* 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
* 有效字符串需满足：
* 左括号必须用相同类型的右括号闭合。
* 左括号必须以正确的顺序闭合。
* 注意空字符串可被认为是有效字符串。
* <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));
}
```