0%

leetcode 678 有效的括号字符串

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

任何左括号 ( 必须有相应的右括号 )。
任何右括号 ) 必须有相应的左括号 ( 。
左括号 ( 必须在对应的右括号之前 )。

  • 可以被视为单个右括号 ) ,或单个左括号 ( ,或一个空字符串。
    一个空字符串也被视为有效字符串。
    字符串大小将在 [1,100] 范围内。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    示例 1:

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

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

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

思路:
做法1:
数据范围不大可以考虑暴力做法:
利用前缀和判断当前序列是否合法(前缀和左括号+1,右括号-1,合法有如下性质:过程中如果出现负数则肯定不合法,过程中前缀和全>=0且整个前缀和==0说明合法)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
bool checkValidString(string s) {
int n = s.size();
return dfs(s,0,n,0);
}
bool dfs(string &s,int start,int &n,int sum){
if(sum<0)return false;
if(start==n && sum==0)return true;
for(int i=start;i<n;i++){
if(s[start]=='('){
if(dfs(s,i+1,n,sum+1))return true;
else return false;
}
else if(s[start]==')'){
if(dfs(s,i+1,n,sum-1))return true;
else return false;
}
else{
if(dfs(s,i+1,n,sum+1))return true;
if(dfs(s,i+1,n,sum-1))return true;
if(dfs(s,i+1,n,sum))return true;
return false;
}
}
return false;
}
};

做法2:
正反向遍历字符串各一次,正向遍历时左括号+星号的出现次数要一直小于等于右括号出现次数。
反向遍历时右括号+星号的次数要一直小于等于左括号,否则不能合法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
bool checkValidString(string s) {
int n=s.size();
int l1=0,r1=0,s1=0,l2=0,r2=0,s2=0;
for(int i=0,j=n-1;i<n;j--,i++){
if(s[i]=='(')l1++;
if(s[i]==')')r1++;
if(s[i]=='*')s1++;
if(s[j]=='(')l2++;
if(s[j]==')')r2++;
if(s[j]=='*')s2++;
if(r1>l1+s1 || l2>r2+s2)return false;
}
return true;
}
};