笔者在解决力扣678题时，分别采用了贪婪法和回溯法对其进行解决。

678. 有效的括号字符串

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

任何左括号 ( 必须有相应的右括号 )。

任何右括号 ) 必须有相应的左括号 ( 。

左括号 ( 必须在对应的右括号之前 )。

  • 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。

一个空字符串也被视为有效字符串。

示例 1:

输入: “()”

输出: True

示例 2:

输入: “(*)”

输出: True

示例 3:

输入: “(*))”

输出: True

注意:

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

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/valid-parenthesis-string

贪婪法

  1. class Solution {
  2. public:
  3.     bool checkValidString(string s) {
  4.         int lo = 0, hi = 0;
  6.         for(auto &ch : s)
  7.         {
  8.             lo += ch == '(' ? 1 : -1;
  9.             hi += ch != ')' ? 1 : -1;
  11.             if(hi < 0)
  12.                 return false;
  14.             lo = max(lo, 0);
  15.         }
  17.         if(lo == 0)
  18.             return true;
  19.         else
  20.             return false;
  21.     }
  22. };

完成一次字符串遍历，因此时间复杂度为O(N)
使用了lo, hi两个变量，因此空间复杂度为O(1)

下图是空间和时间的消耗情况
image.png

回溯法

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;
    }
};

下图是空间的消耗情况

image.png