LeetCode-678. 有效的括号字符串

题目来源

678. 有效的括号字符串

题目详情

给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：

1. 任何左括号 ( 必须有相应的右括号 )。
2. 任何右括号 ) 必须有相应的左括号 ( 。
3. 左括号 ( 必须在对应的右括号之前 )。
4. * 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
5. 一个空字符串也被视为有效字符串。

示例 1:

输入: "()"
输出: True

示例 2:

输入: "(*)"
输出: True

示例 3:

输入: "(*))"
输出: True

注意:

1. 字符串大小将在 [1，100] 范围内。

相似题目

题解分析

解法一：二维动态规划

1. 本题一看题目就知道是一道动态规划相关的题目，而且这个题型与之前遇到的5-最长回文子串以及647-回文子串这两道题目很相似，因为它们都是一种需要考虑中间子串的情况。这是与32-最长有效括号这道题目最大的一个区别，因为LeetCode-32这道题只有左右括号两种字符，所以它可以使用一维的dp数组来表示最长有效括号的长度，但是本题除了左右括号还有一个特殊的'*'号，它可以充当任意一个符号，甚至空字符，这就导致了如果使用一维dp将无法根据前面的状态进行转移。
2. 因此，这里我们借助回文子串的解题思路，定义一个dp数组为boolean[][] dp，其中\(dp[i][j]\)表示（i,j）的子串是否是有效的括号字符串。而它们的状态转移如下：

3. 上面的状态转移方程涉及到两种情况：
   • 第一种，如果i和j所处的字符是合法的括号对，即分别为(和)字符，或者是使用了‘*’替换后的有效括号对，那么\(dp[i][j]\)的状态可以根据\(dp[i+1][j-1]\)来判断。
   • 第二种，如果上述得出的\(dp[i][j]\)是false，那就要进入这种情况的判断了。我们需要遍历i到j之间的字符，看是否可以找到一个字符k，使得（i,k）和（k,j）都是有效的括号字符串，如果能找到说明\(dp[i][j]\)也是合法的括号字符串。
4. 本题需要注意的是，因为我们都是成对来考虑的，所以我们需要对dp数组进行一些特殊的初始化，比如需要分别初始化字符串长度为1和2时候的dp状态，这些状态的判断比较简单，这里就不详细说明了。

class Solution {
    public boolean checkValidString(String s) {
        int n = s.length();
        // dp[i][j]表示以（i,j）的子串是否是有效的括号字符串
        // dp[i][j] = dp[i+1][j-1] || (dp[i][k] && dp[k+1][j])
        boolean[][] dp = new boolean[n][n];
        for(int i=0; i=0; i--){
            char ch1 = s.charAt(i);
            for(int j=i + 2; j