README_EN.md

678. Valid Parenthesis String

中文文档

Description

Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid.

The following rules define a valid string:

• Any left parenthesis '(' must have a corresponding right parenthesis ')'.
• Any right parenthesis ')' must have a corresponding left parenthesis '('.
• Left parenthesis '(' must go before the corresponding right parenthesis ')'.
• '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string "".

 

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "(*)"
Output: true

Example 3:

Input: s = "(*))"
Output: true

 

Constraints:

• 1 <= s.length <= 100
• s[i] is '(', ')' or '*'.

Solutions

Scan twice, first from left to right to make sure that each of the closing brackets is matched successfully, and second from right to left to make sure that each of the opening brackets is matched successfully

Python3

class Solution:
    def checkValidString(self, s: str) -> bool:
        n = len(s)
        left, asterisk = 0, 0
        for i in range(n):
            if s[i] == "(":
                left += 1
            elif s[i] == ")":
                if left > 0:
                    left -= 1
                elif asterisk > 0:
                    asterisk -= 1
                else:
                    return False
            else:
                asterisk += 1
        right, asterisk = 0, 0
        for i in range(n - 1, -1, -1):
            if s[i] == ")":
                right += 1
            elif s[i] == "(":
                if right > 0:
                    right -= 1
                elif asterisk > 0:
                    asterisk -= 1
                else:
                    return False
            else:
                asterisk += 1
        return True

Java

class Solution {
    public boolean checkValidString(String s) {
        int n = s.length();
        char[] a = s.toCharArray();
        int left = 0, asterisk = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] == '(') {
                left++;
            } else if (a[i] == ')') {
                if (left > 0) {
                    left--;
                } else if (asterisk > 0) {
                    asterisk--;
                } else {
                    return false;
                }
            } else {
                asterisk++;
            }
        }
        int right = 0;
        asterisk = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (a[i] == ')') {
                right++;
            } else if (a[i] == '(') {
                if (right > 0) {
                    right--;
                } else if (asterisk > 0) {
                    asterisk--;
                } else {
                    return false;
                }
            } else {
                asterisk++;
            }
        }
        return true;
    }
}

C++

class Solution {
   public:
    bool checkValidString(string s) {
        int n    = s.size();
        int left = 0, asterisk = 0;
        for (int i = 0; i < n; ++i) {
            if (s[i] == '(') {
                ++left;
            } else if (s[i] == ')') {
                if (left > 0)
                    --left;
                else if (asterisk > 0)
                    --asterisk;
                else
                    return false;
            } else {
                ++asterisk;
            }
        }
        int right = 0;
        asterisk  = 0;
        for (int i = n - 1; i >= 0; --i) {
            if (s[i] == ')') {
                ++right;
            } else if (s[i] == '(') {
                if (right > 0)
                    --right;
                else if (asterisk > 0)
                    --asterisk;
                else
                    return false;
            } else {
                ++asterisk;
            }
        }
        return true;
    }
};

Go

func checkValidString(s string) bool {
	n := len(s)
	left, asterisk := 0, 0
	for i := 0; i < n; i++ {
		if s[i] == '(' {
			left++
		} else if s[i] == ')' {
			if left > 0 {
				left--
			} else if asterisk > 0 {
				asterisk--
			} else {
				return false
			}
		} else {
			asterisk++
		}
	}
	asterisk = 0
	right := 0
	for i := n - 1; i >= 0; i-- {
		if s[i] == ')' {
			right++
		} else if s[i] == '(' {
			if right > 0 {
				right--
			} else if asterisk > 0 {
				asterisk--
			} else {
				return false
			}
		} else {
			asterisk++
		}
	}
	return true
}

...