Leetcode刷题100天—678. 有效的括号字符串( 字符串)—day36

╰半橙微兮° 2022-09-14 02:16 167阅读 0赞

前言：

> 作者：神的孩子在歌唱
> 
> 大家好，我叫运智

![image-20210912124448740][]

#### [678. 有效的括号字符串][678.] ####

难度中等325收藏分享切换为英文接收动态反馈

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

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

**示例 1:**

输入: "()"
    输出: True

**示例 2:**

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

**示例 3:**

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

**注意:**

1.  字符串大小将在 \[1，100\] 范围内。

package 字符串;
    
    import java.util.Stack;
    /* * https://leetcode-cn.com/problems/valid-parenthesis-string/ */
    public class _678_有效的括号字符串 { 
    // 通过栈来判断,左括号星号入栈，入栈的元素是他们的下标，遇到右括号就出栈，
    // 最后判断栈是否为空，如果不为空左括号下标是否大
        public boolean checkValidString(String s) { 
    // 设置两个栈
        	Stack<Integer> left_stack=new Stack<>();
        	Stack<Integer> planet_stack=new Stack<>();
    // 循环下标如果是(和*就入栈,是）就取出(匹配,如果(栈为空,就取出*做匹配,两个都为空就返回false
        	for(int i=0;i<s.length();i++) { 
        		char character=s.charAt(i);
    // 如果是左括号就存入下标
        		if (character=='(') { 
    				left_stack.push(i);
    			}else if(character=='*') { 
    				planet_stack.push(i);
    			}else { 
    // 否则如果（栈不为空就匹配）
    				if (!left_stack.isEmpty()) { 
    					left_stack.pop();
    				}else if (!planet_stack.isEmpty()) { 
    					planet_stack.pop();
    				}else { 
    					return false;
    				}
    			}
    
        	}
    // 上面的是匹配了),可是如果栈left和planet不为空,还得要通过planet匹配
    		while(!left_stack.isEmpty()&&!planet_stack.isEmpty()) { 
    			int left=left_stack.pop();
    			int planet=planet_stack.pop();
    // 如果left的下标大于planet下标，说明在 plant后面，无法匹配
    			if (left>planet) { 
    				return false;
    			}
    		}
    // 如果遍历完毕没有异常,且left为空，就返回true否则false
        	
        	return left_stack.isEmpty();
        }
    }

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114
> 
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[image-20210912124448740]: /images/20220828/85ca2aa4f6034cdeb9295f102181038b.png
[678.]: https://leetcode-cn.com/problems/valid-parenthesis-string/