LWC 50：678. Valid Parenthesis String

LWC 50：678. Valid Parenthesis String

Problem:

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:

• 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.
• 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]. Discuss

思路： 采用暴力搜索，真正需要遍历的状态是”*”，每次遇到星，都有三种状态：1. 不做任何操作，2. 左括号+1， 3. 右括号+1，合法状态为左括号始终大于等于右括号，且最终输出left == right。

代码如下：

    public boolean checkValidString(String s) {
        return robot(s.toCharArray(), 0, 0, 0);
    }

    boolean robot(char[] cs, int i, int left, int right) {
        if (i >= cs.length) {
            return left == right;
        }
        for (int j = i; j < cs.length; ++j) {
            if (cs[j] == '(')
                left++;
            else if (cs[j] == ')') {
                right++;
                if (right > left) return false;
            } 
            else {
                return robot(cs, j + 1, left, right) || robot(cs, j + 1, left + 1, right)
                        || robot(cs, j + 1, left, right + 1);
            }
        }
        return left == right;
    }