678 有效的括号字符串

本文最后更新于：2021年4月4日 下午

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

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

示例 1:

1
2
输入: "()"
输出: True

示例 2:

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

示例 3:

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

注意:

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

Solution

参考：@zrita

  • 贪心算法

  • 有效的字符串，即从左向右看是有效的，从右向左看也是有效的

  • 如果在遍历过程中，left 或者 right 小于0，则是无效

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// @lc code=start
class Solution {
public:
    bool checkValidString(string s) {
        int left = 0, right = 0;
        for (int i = 0; i < s.size(); ++i) {
            left += (s[i] == ')' ? -1 : 1);				//从左向右
            right += (s[s.size()-1-i] == '(' ? -1 : 1); //从右向左
            if (left < 0 || right < 0)					//无效
                return false;
        }
        return true;
    }
};
// @lc code=end
algo leetcode 算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！