678. 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: 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是不是为空。

    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 数来记录。

    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

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;