678. Valid Parenthesis String

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

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 ‘*’.

Code

Counting

• **))) - max = -1, min = 0 - false
• ((()* - max = 3, min = 1 - false
• (*) - max = 1, min = 0 - true
• (*)) - max = 0, min = 0 - true
• ((** - max = 4, min = 0 - true

class Solution {
    public boolean checkValidString(String s) {
        int min = 0; // 最少需要 ) 的个数
        int max = 0; // 最多需要 ) 的个数
        
        for (char c : s.toCharArray()) {
            if (c == '(') {
                min++;
                max++;
            } else if (c == ')') {
                if(min > 0) min--; // (*)) - true, ((*)(*))((* - false
                max--;
            } else if (c == '*') {
                if(min > 0) min--; // 看作 ) - ()*** - true
                max++; // 看作 (
            }
            // ) 多于 ( 和 * 数量, 例: **)))
            if (max < 0) return false; 
        }
        
        return min == 0;
    }
}

DP

两种情况

• 情况1: ((((((()))))))
• 情况2: (())(())

class Solution {
    public boolean checkValidString(String s) {
        int length = s.length();
        boolean[][] dp = new boolean[length][length];

        for (int len = 1; len <= length; len++) {
            for (int i = 0; i + len <= length; i++) {
                int j = i + len - 1;
                // dp[i][i]只有在*时才算有解
                if (i == j) {
                    dp[i][j] = s.charAt(i) == '*';
                    continue;
                }
                // 情况1: 当前位置有效, 看内部是不是有效
                if ((s.charAt(i) == '*' || s.charAt(i) == '(')
                        && (s.charAt(j) == '*' || s.charAt(j) == ')')) {
                    if (len == 2 || dp[i + 1][j - 1]) {
                        dp[i][j] = true;
                        continue;
                    }
                }
                // 情况2: 以当前位置为分割点, 看左右是不是有效
                for (int k = i; k < j; ++k) {
                    if (dp[i][k] && dp[k + 1][j]) {
                        dp[i][j] = true;
                        break;
                    }
                }
            }
        }

        return dp[0][length - 1];
    }
}