[LeetCode]678. 有效的括号字符串、20. 有效的括号（栈）
2024-10-09 12:14:05
题目 678. 有效的括号字符串
给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：
任何左括号 ( 必须有相应的右括号 )。
任何右括号 ) 必须有相应的左括号 ( 。
左括号 ( 必须在对应的右括号之前 )。
* 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
一个空字符串也被视为有效字符串。
示例 1:
输入: "()"
输出: True
示例 2:
输入: "(*)"
输出: True
示例 3:
输入: "(*))"
输出: True
注意:
字符串大小将在 [1，100] 范围内。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parenthesis-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解
- 两个栈，left栈装（，star栈装*。
- 当遇到），优先pop left栈，若为空则pop*栈，若都为空则返回false。
- 接下来要处理若两栈内有剩余的情况，两栈同时弹出配对，若left栈弹出元素索引>star栈弹出元素索引，则直接返回false。
- 最后检查left栈为空则ok，栈可以有任意剩余，因为偶数个可配对，1个*可以作为空串。
代码
import java.util.Stack;
class Solution {
public boolean checkValidString(String s) {
Stack<Integer> left = new Stack<>();
Stack<Integer> star = new Stack<>();
for(int i=0;i<s.length();++i){
char c = s.charAt(i);
if(c=='('){
left.push(i);
}else if(c=='*'){
star.push(i);
}else if(!left.empty()){
left.pop();
}else if(!star.empty()){
star.pop();
}else{
return false;//
}
}
while(!left.empty()&&!star.empty()){
if(left.pop()>star.pop()){
return false;
}
}
System.out.print(star.size());
return left.empty();
}
}
题目
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解
- 使用map存括号的对应关系。
- 使用特殊字符入栈底，并设置对应关系，省去栈为空的特殊判断。
- 使用栈解决。
代码
class Solution {
public static boolean isValid(String s) {
if(s==null){
return true;
}
Map<Character,Character> map = new HashMap<>();
map.put('(',')');
map.put('[',']');
map.put('{','}');
map.put('@','@');
LinkedList<Character> stack = new LinkedList<>();
stack.addLast('@');
for(Character c : s.toCharArray()){
if(map.containsKey(c)){
stack.addLast(c);
}else
if(c!=map.get(stack.removeLast())){
return false;
}
}
}
return stack.size()==1;
}
}
最新文章
- json,pickle
- Matlab(1) -- Matlab清屏命令
- 常用的java类型转json的转换类
- 模式的混合-我們真的需要一次一次的讀配置嗎-MultitonPrototypeFactoryMethod
- 如何使用mybatis《三》
- C#加密算法总结
- bzoj 3289 Mato的文件管理（莫队算法+BIT）
- 同步or异步
- Android 金融项目整理
- [背景分离] 识别移动物体基于高斯混合 MOG
- LeetCode之Max Points on a Line Total
- javascript 正则介绍
- python安装第三方库的三种方法
- element-UI使用中：el-input type为textarea时@change无法触发？
- angular.equals()
- ionic3开发环境的搭建 记录！
- ftp修改上传后目录、文件权限问题 aix
- cpu高 load 高 内存高 io 高怎么排查
- linux引导系统
- mysql 5.6 与5.7安装