网站建设课程设计心得体会,绵阳优化网站排名,网络推广主要内容,购买服务器做网站1. 题目
给定一个只包含三种字符的字符串#xff1a;#xff08; #xff0c;#xff09; 和 *#xff0c;写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则#xff1a;
任何左括号 ( 必须有相应的右括号 )。任何右括号 ) 必须有相应的左括号 ( 。…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--;elsereturn 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--;elsereturn false;}}return true;}
};2.2 栈
两个栈分别存储(和*的下标
class Solution {
public:bool checkValidString(string s) {stackint l;stackint 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();elsestar.pop();}}while(!l.empty() !star.empty()){if(l.top() star.top())// * ( 不能匹配return false;l.pop();star.pop();}return l.empty();}
};
