双栈_leetcode.678.有效地括号字符串

🌸题目

🍁给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：

• 任何左括号 ( 必须有相应的右括号 )。
• 任何右括号 ) 必须有相应的左括号 ( 。
• 左括号 ( 必须在对应的右括号之前 )。
• *可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
• 一个空字符串也被视为有效字符串。

示例:

输入: "()"
输出: True
示例 2:

输入: "(*)"
输出: True
示例 3:*

*输入: "( *))"
输出: True

注意:字符串大小将在 [1，100] 范围内。

分析

这道题是经典的括号型，第一想到的应该是双栈

🌸解法一：DFS

• 先编写无 * 情况的代码
  • count 记录左括号个数
  • 遇左则增，遇右则减
  • 若不够减则 return false
• 补充有 * 的情况
  • 分别开出三种可能继续探索
  • 任何一种成了即可
• 时间复杂度分析
  • 代码结构涉及循环，可能有递归，故可用最好、最好、加权平均时间- 复杂度表示
  • 若不考虑中途提前结束（递归终止 或 左括号不足匹配右括号的终止）
    • 最好 O(n)，无星号的情况
    • 最坏 O(3^n^),全是星号的情况
  • 若考虑中途提前结束
    • 最好 O(1)，右括号开头
      最坏 O(3^n^),全星号的情况
    • 求和各情况的 概率 * 此情况要遍历的元素个数

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();
}

最后，不经历风雨,怎能在计算机的大山之顶看见彩虹呢！ 无论怎样，相信明天一定会更好！！！！！