LeetCode 678. 有效的括号字符串（栈）
LeetCode 678. 有效的括号字符串（栈）
Michael阿明
发布于 2020-07-13 17:13:35
发布于 2020-07-13 17:13:35
文章被收录于专栏：Michael阿明学习之路
1. 题目
给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：
- 任何左括号 ( 必须有相应的右括号 )。
- 任何右括号 ) 必须有相应的左括号 ( 。
- 左括号 ( 必须在对应的右括号之前 )。
*可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。- 一个空字符串也被视为有效字符串。
示例 1:
输入: "()"
输出: True
示例 2:
输入: "(*)"
输出: True
示例 3:
输入: "(*))"
输出: True来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/valid-parenthesis-string 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
2.1 正反两次扫描
class Solution {
public:
bool checkValidString(string s) {
int i, star = 0, left = 0, right = 0;
for(i = 0; i < s.size(); ++i)
{
if(s[i] == '(')
left++;
else if(s[i] == '*')
star++;
else if(s[i] == ')')
{
if(left)
left--;
else if(star)
star--;
else
return false;
}
}
left = right = star = 0;
for(i = s.size()-1; i >= 0; --i)
{
if(s[i] == ')')
right++;
else if(s[i] == '*')
star++;
else if(s[i] == '(')
{
if(right)
right--;
else if(star)
star--;
else
return false;
}
}
return true;
}
};
在这里插入图片描述
2.2 栈
两个栈，分别存储(和*的下标
class Solution {
public:
bool checkValidString(string s) {
stack<int> l;
stack<int> star;
for(int i = 0; i < s.size(); ++i)
{
if(s[i] == '(')
l.push(i);
else if(s[i] == '*')
star.push(i);
else
{
if(l.empty() && star.empty())
return false;//不够匹配
if(!l.empty())
l.pop();
else
star.pop();
}
}
while(!l.empty() && !star.empty())
{
if(l.top() > star.top())// * ( 不能匹配
return false;
l.pop();
star.pop();
}
return l.empty();
}
};本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020/01/06 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
