欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  科技

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

程序员文章站 2022-06-26 17:58:33
栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。...

题目

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

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

示例:

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

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

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

分析

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

解法一:DFS

  • 先编写无 * 情况的代码
    • 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