给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：
- 任何左括号 ( 必须有相应的右括号 )。
- 任何右括号 ) 必须有相应的左括号 ( 。
- 左括号 ( 必须在对应的右括号之前 )。
- *可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
- 一个空字符串也被视为有效字符串。
示例:
输入: " ( ) "
输出: True
示例 2:输入: " ( * ) "
输出: True
示例 3:**输入: " ( * ) ) "
输出: True
注意:字符串大小将在 [1，100] 范围内。
这道题是经典的括号型，第一想到的应该是双栈
- 先编写无 * 情况的代码
- count 记录左括号个数
- 遇左则增，遇右则减
- 若不够减则 return false
- 补充有 * 的情况
- 分别开出三种可能继续探索
- 任何一种成了即可
- 时间复杂度分析
- 代码结构涉及循环，可能有递归，故可用最好、最好、加权平均时间- 复杂度表示
- 若不考虑中途提前结束（递归终止 或 左括号不足匹配右括号的终止）
- 最好 O(n)，无星号的情况
- 最坏 O(3n),全是星号的情况
- 若考虑中途提前结束
- 最好 O(1)，右括号开头
最坏 O(3n),全星号的情况- 求和各情况的 概率 * 此情况要遍历的元素个数
我要评论 public boolean checkValidString(String s) {
if(s.isEmpty()) {
return true;
}
return check(s, 0, 0);
}
private boolean check(String s, int start, int count) {
// TODO Auto-generated method stub
if(count < 0) {
return false;
}
// count记录（ 的个数
for(int i = start; i < s.length(); i++) {
char c = s.charAt(i);
if(c == '(') {
count++;
}else if(c == ')') {
if(count-- == 0) { //若（ 为0，表示右括号多了，没有多余的左括号进行匹配
return false;
}
}else {
return check(s, i + 1, count + 1) || //*作为(
check(s, i + 1, count - 1) || //*作为)
check(s, i + 1, count); //*作为null
}
}
return count == 0;
}
- 与方法一神似
- 无需每种情况都细分考虑，只需关注 左括号至少几个、至多几个
- 遇左则至多/至少都增加
- 遇右则至多/至少都减少
- 若至多
max都不够抵右括号，则return false- 遇 *则可能减少/不变/增多，即
min--;max++;
- 若至少
min小于 0 ，说明此分支走不通，需剪枝- 类似方法一中的递归终止条件
if (count < 0) return false;- 最终要求左括号必须无剩余
min == 0;
min < 0的情况在上一条思路中剪枝了
public boolean checkValidString2(String s) {
int min = 0, max = 0; // 维护左括号的数量范围[min,max]
for(char c : s.toCharArray()) {
if(c == '(') {
min++;
max++;
}else if(c == ')'){
if(min > 0) { //至少值 的左括号 大于0，则至少值减一
min--;
}
if(max-- == 0) { //最大左括号数量不够匹配右括号
return false;
}
}else {
if(min > 0) { //*作为右括号进行抵消
min--;
}
max++; //*作为左括号，至大值加一
}
}
return min == 0; //只需要判断至少的左括号有多余不
}
- 极端假设替换为全左或全右，双向遍历验证
- 假设所有
*为(
- 因左括号必须在配对的左边，故从左向右遍历，看是否足够覆盖所有
')'- 假设所有
*都为')'
- 因右括号必须在配对的右边，故从右向左遍历，看是否足够覆盖所有
'('
java
public boolean checkValidString3(String s) {
int l = 0;
for(int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if(c != ')') {
l++;
}else {
if(l-- == 0) { //意味着右括号多了，没有多余的左括号进行匹配
return false;
}
}
}
//进行提前特判，若能够匹配则退出
if(l == 0) {
return true;
}
//*全部作为右括号，从右往左进行遍历匹配
int r = 0;
for(int i = s.length() - 1; i >= 0; i--) {
char c = s.charAt(i);
if(c != '(') {
r++;
}else {
if(r-- == 0) { //意味着左括号多了，无法完成匹配
return false;
}
}
}
//此时左括号没有富余
return true;
}
- 括号匹配问题的经典解法
- 栈存放的是索引
- 一栈存左括号，一栈存星号
- 遍历过程中，同时判断是否有足够的右括号使他们出栈
- 优先抵消左括号（
贪心思想）- 两栈同时出栈并判断，要求所有左括号，都有 其右边索引的星号 能使其抵消
- 左括号不能还有富余
public boolean checkValidString4(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.isEmpty()) { //优先出栈左括号
left.pop();
}else if(!star.isEmpty()) {
star.pop();
}else {
return false;
}
}
}
//若左栈和星栈扔不为空，则将双栈同时出栈，用*代替）匹配（
while(!left.isEmpty() && !star.isEmpty()) {
if(left.pop() > star.pop()) { //若左栈的下标在星栈的右边，无法进行匹配
return false;
}
}
return left.isEmpty();
}
本文地址：https://blog.csdn.net/weixin_45333934/article/details/107311377
如对本文有疑问， 点击进行留言回复！！
数字与信号处理实验6 有限冲激响应(FIR)数字滤波器的设计
【计算机体系结构 / 并行与分布计算 / 存储系统】 2019年-中国计算机学会推荐国际学术会议和期刊目录（一）
荐 《操作系统导论》学习笔记（七）：内存虚拟化 (机制及策略)
网友评论