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

题目

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

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

示例:

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

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

*输入: " ( * ) ) "
输出: True
注意:字符串大小将在 [1，100] 范围内。

分析

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

解法一：DFS

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

	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