笔者在解决力扣678题时,分别采用了贪婪法和回溯法对其进行解决。
678. 有效的括号字符串
给定一个只包含三种字符的字符串:( ,) 和 *,写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则:
任何左括号 ( 必须有相应的右括号 )。
任何右括号 ) 必须有相应的左括号 ( 。
左括号 ( 必须在对应的右括号之前 )。
- 可以被视为单个右括号 ) ,或单个左括号 ( ,或一个空字符串。
一个空字符串也被视为有效字符串。
示例 1:
输入: “()”
输出: True
示例 2:
输入: “(*)”
输出: True
示例 3:
输入: “(*))”
输出: True
注意:
字符串大小将在 [1,100] 范围内。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/valid-parenthesis-string
贪婪法
在这里,需要根据题目来弄明白条件,式子成立的条件是:左括号不可能是小于0的,正常情况下,如果左括号小于0,那肯定是使用的*号作为左括号的次数太多了,而且右括号不能小于0,如果为0说明,右括号太多了,右括号右边的左括号不可能来挽救这个右括号了。
class Solution {
public:
bool checkValidString(string s) {
int lo = 0, hi = 0;
for(auto &ch : s)
{
lo += ch == '(' ? 1 : -1;
hi += ch != ')' ? 1 : -1;
if(hi < 0)
return false;
lo = max(lo, 0);
}
if(lo == 0)
return true;
else
return false;
}
};
完成一次字符串遍历,因此时间复杂度为O(N)
使用了lo, hi两个变量,因此空间复杂度为O(1)
下图是空间和时间的消耗情况
回溯法
class Solution {
public:
map<pair<stack<char>, string>, bool>store;
bool subcheck(stack<char>par, string s)
{
if(!par.empty() && s == "")
return false;
if(par.empty() && s == "")
return true;
pair<stack<char>, string>curpair{par, s};
if(store.find(curpair) != store.end())
return store[curpair];
for(int i = 0; i < s.size(); i++)
{
if(s[i] == '(')
{
par.push('(');
}
else if(s[i] == ')')
{
if(par.empty())
{
store[curpair] = false;
return false;
}
else
{
par.pop();
}
}
else
{
string tmp = s.substr(i + 1, s.size() - i - 1);
store[curpair] = (subcheck(par, '(' + tmp) || subcheck(par, tmp) || subcheck(par, ')' + tmp));
return store[curpair];
}
}
if(par.empty())
{
store[curpair] = true;
return true;
}
else
{
store[curpair] = false;
return false;
}
}
bool checkValidString(string s) {
int size = s.size();
if(size == 0)
return true;
if(size == 1)
{
if(s == "*")
return true;
else
return false;
}
stack<char>par;
for(int i = 0; i < size; i++)
{
if(s[i] == '(')
par.push('(');
else if(s[i] == ')')
{
if(par.empty())
return false;
else
par.pop();
}
else
{
string tmp = s.substr(i + 1, s.size() - i - 1);
return (subcheck(par, '(' + tmp) || subcheck(par, tmp) || subcheck(par, ')' + tmp));
}
}
if(par.empty())
return true;
else
return false;
}
};
下图是空间的消耗情况