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

678. 有效的括号字符串

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

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

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

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

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

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

示例 1:

输入: “()”

输出: True

示例 2:

输入: “(*)”

输出: True

示例 3:

输入: “(*))”

输出: True

注意:

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

来源：力扣（LeetCode）

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

贪婪法
在这里，需要根据题目来弄明白条件，式子成立的条件是：左括号不可能是小于0的，正常情况下，如果左括号小于0，那肯定是使用的*号作为左括号的次数太多了，而且右括号不能小于0，如果为0说明，右括号太多了，右括号右边的左括号不可能来挽救这个右括号了。

  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

回溯法

  1. class Solution {
  2. public:
  3.     map<pair<stack<char>, string>, bool>store;
  5.     bool subcheck(stack<char>par, string s)
  6.     {
  7.         if(!par.empty() && s == "")
  8.         return false;
  10.         if(par.empty() && s == "")
  11.             return true;
  13.         pair<stack<char>, string>curpair{par, s};
  15.         if(store.find(curpair) != store.end())
  16.             return store[curpair];
  18.         for(int i = 0; i < s.size(); i++)
  19.         {
  20.             if(s[i] == '(')
  21.             {
  22.                 par.push('(');
  23.             }
  24.             else if(s[i] == ')')
  25.             {
  26.                 if(par.empty())
  27.                 {
  28.                     store[curpair] = false;
  29.                     return false;
  30.                 }
  31.                 else
  32.                 {
  33.                     par.pop();
  34.                 }
  35.             }
  36.             else
  37.             {
  38.                 string tmp = s.substr(i + 1, s.size() - i - 1);
  39.                 store[curpair] = (subcheck(par, '(' + tmp) || subcheck(par, tmp) || subcheck(par, ')' + tmp));
  40.                 return store[curpair];
  41.             }
  42.         }
  44.         if(par.empty())
  45.         {
  46.             store[curpair] = true;
  47.             return true;
  48.         }
  49.         else
  50.         {
  51.             store[curpair] = false;
  52.             return false;
  53.         }
  54.     }
  56.     bool checkValidString(string s) {
  57.         int size = s.size();
  59.         if(size == 0)
  60.             return true;
  62.         if(size == 1)
  63.         {
  64.             if(s == "*")
  65.                 return true;
  66.             else
  67.                 return false;
  68.         }
  70.         stack<char>par;
  72.         for(int i = 0; i < size; i++)
  73.         {
  74.             if(s[i] == '(')
  75.                 par.push('(');
  76.             else if(s[i] == ')')
  77.             {
  78.                 if(par.empty())
  79.                     return false;
  80.                 else
  81.                     par.pop();
  82.             }
  83.             else
  84.             {
  85.                 string tmp = s.substr(i + 1, s.size() - i - 1);
  86.                 return (subcheck(par, '(' + tmp) || subcheck(par, tmp) || subcheck(par, ')' + tmp));
  87.             }
  88.         }
  90.         if(par.empty())
  91.             return true;
  92.         else
  93.             return false;
  94.     }
  95. };

下图是空间的消耗情况

image.png