LeetCode Valid Parenthesis String

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。

Leave a Reply

Your email address will not be published. Required fields are marked *