678. Valid Parenthesis String

Given a string containing only three types of characters: ‘(‘, ‘)’ and ‘*’, write a function to check whether this string is valid. We define the validity of a string by these rules:

1. Any left parenthesis '(' must have a corresponding right parenthesis ')'.
2. Any right parenthesis ')' must have a corresponding left parenthesis '('.
3. Left parenthesis '(' must go before the corresponding right parenthesis ')'.
4. '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.
5. An empty string is also valid.

Example 1:

Input: "()"
Output: True

Example 2:

Input: "(*)"
Output: True

Example 3:

Input: "(*))"
Output: True

Note:

1. The string size will be in the range [1, 100].

---

给定一个字符串，里面包含左括号、右括号和星号，星号可以表示左括号、右括号或空格。问这个字符串是否可能是一个合法的括号字符串。

这题有点难理解，直接看题解。

解法1，两遍扫描法，好理解。星号有3种情况，第一次假设星号全部是左括号，如果能满足左括号总数≥右括号总数，说明字符串中的右括号不会太多，用星号加原有的左括号能抵消掉所有的右括号。第二次假设星号全部是右括号，如果能满足右括号总数≥左括号总数，说明字符串中的左括号不会太多，用星号加原有的右括号能抵消掉所有的左括号。由于星号还可以表示空格，所以如果上述两种情况都满足，则多于的星号可以换成空格。

该解法本质上考虑了两种极端情况，而合法解肯定在这两个极端之间。

在以上两种情况的判断过程中，扫描的时候如果不满足条件可以提前终止。比如假设星号全部是左括号时，从左往右扫描字符串，如果出现右括号数大于左括号数的情况，直接返回false。因为我已经把所有星号假设为左括号了，但还是满足不了右括号，说明右括号太多了，非法。类似的，当假设星号为右括号时，从右往左扫描，也可以提前终止。完整代码如下：

class Solution {
public:
	bool checkValidString(string s) {
		int left_balance = 0;
		for (int i = 0; i < s.size(); ++i) {
			if (s[i] == '(' || s[i] == '*')++left_balance;
			else --left_balance;
			if (left_balance < 0)return false;
		}
		if (left_balance == 0)return true;

		int right_balance = 0;
		for (int i = s.size() - 1; i >= 0; --i) {
			if (s[i] == ')' || s[i] == '*')++right_balance;
			else --right_balance;
			if (right_balance < 0)return false;
		}
		return true;
	}
};

本代码提交AC，用时0MS。

解法2，一遍扫描法，不太好理解。定义字符串中多余出来的左括号数的最小值min_left和最大值max_left。从左往右扫描字符串，遇到左括号，则min_left和max_left都要加一；遇到右括号，则min_left和max_left都要减一；遇到星号时，把它当做右括号，则min_left减一，把它当做左括号，则max_lfet加一。如果[min_left, max_left]区间包括0，则说明字符串有可能是合法的，因为多余的左括号等于0的话，说明左右括号平衡了。完整代码如下：

class Solution {
public:
	bool checkValidString(string s) {
		int min_left = 0, max_left = 0;
		for (int i = 0; i < s.size(); ++i) {
			min_left += (s[i] == '(' ? 1 : -1);
			max_left += (s[i] != ')' ? 1 : -1);
			if (max_left < 0)break;
			min_left = max(min_left, 0);
		}
		return min_left == 0;
	}
};

本代码提交AC，用时0MS。