# 678. Valid Parenthesis String

[**678. Valid Parenthesis String**](https://leetcode.com/problems/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:**\
The string size will be in the range \[1, 100].

***My Solutions:***

星号可以作为左括号、右括号、empty string。那么星号什么时候都能当括号来用吗，来看两个例子: 

* \*): 星号可以当左括号来用
* \*(: 论星号当左括号，右括号，还是空，\*( 都是不对的

因此，不能发生星号在(的前面，同时(的后面没有)的情况。只要星号在右括号前面，就一定可以消掉右括号。所以当遇到右括号时，就算此时之前没有左括号在stack里，只要之前有\*出现过，就可以用\*来当左括号使用。

方法1：用一个char stack只记录左括号，用一个counter记录\*的数量

* 碰到左括号：push进去左括号。
* 碰到右括号：
  * 如果stack里还有左括号，pop出来
  * 如果stack里没有了，但是\*的counter>0, counter--，因为\*可以当做左括号使用
  * 不然直接返回false
* 碰到\*：
  * 先检查stack里有没有左括号，如果有，就先pop左括号出来，\*的counter++。当做把这个stack里一个左括号用\*替代的右括号取消掉。
  * 无论如何，再次counter++，因为当前这个\*可以将来作为左括号使用。

最后检查stack是不是为空。

```java
    public boolean checkValidString(String s) {
        int len = s.length(), star = 0;
        Stack <Character> stack = new Stack();
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(c); // 只记录左括号
            } else if (c == ')') {
                if (!stack.isEmpty()) {
                    stack.pop(); // 消掉一个右括号
                } else if (star > 0){ // 这个*是可以消掉的
                    star--;
                } else {
                    return false;
                }
            } else if (c == '*') {
                if (!stack.isEmpty()) {
                    stack.pop();
                    star++;
                } 
                star++;
            }
        }
        if (stack.isEmpty()) return true;
        return false;
    }
```

方法2：优化上面的方法，不需要stack来记录左括号，只要一个int 数来记录。

```java
    public boolean checkValidString(String s) {
        int stack = 0, star = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack++;
            } 
            else if (c == ')') {
                if (stack > 0) {
                    stack--;
                } else if (star > 0) {
                    star--;
                } else {
                    return false;
                }
            } else if (c == '*') {
                if (stack > 0) {
                    stack--;
                    star++;
                }
                star++;

        }
        if (stack == 0) return true;
        return false;
    }
```

方法3：用two pointer的方法。

* 一个int left记录从左边开始，遇到\*和左括号就+1，遇到右括号就-1，代表从左开始，\*和左括号的数量大于右括号的数量
* 一个int right记录从右边开始，遇到\*和右括号就+1，遇到左括号就-1，代表从右开始，\*和右括号的数量大于左括号的数量
* 在for loop的每一次循环之中检查left和right有没有小于0的值，如果有，说明把星号替代成括号也消除不了相对应的括号，return false

```java
int length = s.length() - 1;
int left = 0, right = 0;
for (int i = 0; i <= length; i++)
{
	if (s[i] == '*' || s[i] == '(') left++;
	else left--;
	
	if (s[length - i] == '*' || s[length - i] == ')') right++;
	else right--;
	
	if (left < 0 || right< 0) return false;
}
return true;
```