题目

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

任何左括号 ( 必须有相应的右括号 )。
任何右括号 ) 必须有相应的左括号 ( 。
左括号 ( 必须在对应的右括号之前 )。
* 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
一个空字符串也被视为有效字符串。

示例：

输入: "()"
输出: True

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

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

解答 & 代码

解法 0：递归回溯（超时）

class Solution {
private:
    bool backTrace(string s, int idx, int leftCnt, int rightCnt)
    {
        // 递归结束条件 1：字符串遍历结束，返回左括号数是否等于右括号数
        if(idx == s.size())
            return leftCnt == rightCnt;
        // 如果之前已遍历的字符串中的右括号数 > 左括号数，肯定不合法，返回 false
        if(rightCnt > leftCnt)
            return false;
        // 如果当前是左括号
        if(s[idx] == '(')
            return backTrace(s, idx + 1, leftCnt + 1, rightCnt);
        // 如果当前是右括号
        else if(s[idx] == ')')
            return backTrace(s, idx + 1, leftCnt, rightCnt + 1);
        // 如果当前是星号
        else if(s[idx] == '*')
            return backTrace(s, idx + 1, leftCnt + 1, rightCnt) || 
                    backTrace(s, idx + 1, leftCnt, rightCnt + 1) ||
                    backTrace(s, idx + 1, leftCnt, rightCnt);
        else
            return false;
    }
public:
    bool checkValidString(string s) {
        return backTrace(s, 0, 0, 0);
    }
};

解法二：栈

[简单] 20. 有效的括号
类似上面这道题，只是多了星号要处理

左括号栈 + 星号栈（两个栈都存储对应的下标）

遍历字符串
1. 如果当前是左括号，则将当前下标存入左括号栈
2. 如果当前是星号，则将当前下标存入星号栈
3. 如果当前是右括号
  1. 优先和左括号匹配，及如果左括号栈不为空，则弹出左括号栈栈顶元素
  2. 若左括号栈为空，则和星号匹配（将星号当作左括号）。如果星号栈不为空，则弹出星号栈栈顶
  3. 如果两个栈都为空，则无法匹配，直接返回 false
匹配剩余左括号，即如果左括号栈不为空，则将星号当作右括号，和左括号栈中的剩余左括号匹配
1. 如果星号栈为空，则无法匹配，直接返回 false
2. 如果星号栈栈顶下标小于左括号栈栈顶下标，则无法匹配，直接返回 false
3. 否则，能够匹配，弹出两个栈栈顶元素

最后左括号栈为空，返回 true（不论星号栈是否为空，若星号栈还有元素，则剩余星号当作空字符即可）

class Solution {
public:
 bool checkValidString(string s) {
     stack<int> leftS;   // 存储左括号对应下标的栈
     stack<int> starS;   // 存储星号对应下标的栈
     // 1. 遍历字符串
     for(int i = 0; i < s.size(); ++i)
     {
         // 1.1 如果当前是左括号，则将当前下标存入左括号栈
         if(s[i] == '(')
             leftS.push(i);
         // 1.2 如果当前是星号，则将当前下标存入星号栈
         else if(s[i] == '*')
             starS.push(i);
         // 1.3 如果当前是右括号
         else if(s[i] == ')')
         {
             // a. 优先和左括号匹配，及如果左括号栈不为空，则弹出左括号栈栈顶元素
             if(!leftS.empty())
                 leftS.pop();
             // b. 若左括号栈为空，则和星号匹配（将星号当作左括号）
             // 如果星号栈不为空，则弹出星号栈栈顶
             else if(!starS.empty())
                 starS.pop();
             // c. 如果两个栈都为空，则无法匹配，直接返回 false
             else
                 return false;
         }
     }
     // 2. 将星号当作右括号，和左括号栈中的剩余左括号匹配
     while(!leftS.empty())
     {
         // 如果左括号栈不为空，而星号栈为空 or 星号栈栈顶下标小于左括号栈栈顶下标
         // 则无法匹配，直接返回 fasle
         if(starS.empty() || starS.top() < leftS.top())
             return false;
         // 否则，能够匹配，弹出两个栈栈顶
         leftS.pop();
         starS.pop();
     }
     // 3. 最后左括号栈为空，返回 true
     return true;
 }
};

复杂度分析：设字符串 s 长为 N

时间复杂度 O(N)：
空间复杂度 O(N)：

执行结果：

执行结果：通过
执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
内存消耗：6 MB, 在所有 C++ 提交中击败了 68.67% 的用户

hot 100

[中等] 678. 有效的括号字符串

题目

解答 & 代码

解法 0：递归回溯（超时）

解法二：栈