题目描述

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:

1. The string size will be in the range [1, 100].
   题意：给一个只包含左右括号和星号的字符串，其中星号可以被看作是左括号，右括号或者为空。请问这个括号串是否合法。

算法1

(暴力搜索) $O(3^n)$

题解1:dfs遍历所有可能的情况。时间复杂度$N*3^N$

class Solution {
public:
    bool checkValidString(string s) {
        return dfs(s,0,s.length());
    }
    bool dfs(string s,int i,int n)
    {
        if(i == n)
            return valid(s,n);
        else if(s[i] == '(' || s[i] == ')')
        {
            return dfs(s,i + 1, n);
        }else
        {
            for(char c:{'(',')',' '})
            {
                s[i] = c;
                if(dfs(s,i + 1,n))
                    return true;
            }
        }
        return false;
    }
    bool valid(string s,int n)
    {
        int bal = 0;
        for(int i = 0 ; i < n;i ++)
        {
            if(s[i] == '(') bal ++;
            if(s[i] == ')') bal --;
            if(bal < 0) break;
        }
        return bal == 0;
    }
};

算法2

(动态规划) $O(n^3)$

题解2:动态规划，状态表示dp[i][j]表示s[i:j]是否合法。时间复杂度$O(N^3)$

状态初始化：如果s[i] ='*',dp[i][i] = true，因为此时可以把其看成空格。如果s[i] = '*' | '(' && s[i + 1] == '*' | ')'，则dp[i][i + 1] = true。然后开始依次计算长度为3,4,...,n的所有字符串是否合法。

状态转移：

1. s[i] = '*' && dp[i + 1][j] == true，那么dp[i][j]合法，将其看成空格。
2. s[i] = '*' | '('，那么遍历i+1 <= k <= j，如果s[k] == '*' | ')'，并且dp[i + 1][k - 1] = true && dp[k + 1][j] == true，那么dp[i][j] = true。
3. s[i] = ')'，dp[i][j] = false

    bool checkValidString(string s) {
        int n = s.length();
        if(n == 0) return true;
        vector<vector<bool>> dp(n,vector<bool>(n,false));
        for(int i = 0 ; i < n ; i ++)
        {
            if(s[i] == '*') dp[i][i] = true;
            if(i < n - 1 && (s[i] == '(' || s[i] == '*') && (s[i + 1] == '*' || s[i + 1] == ')'))
                dp[i][i + 1] = true;
        }
        for(int len = 2; len < n ; len ++)
        {
            for(int i = 0 ;i + len < n ;i ++)
            {
                if(s[i] == '*' && dp[i + 1][i +len] == true)
                {
                    dp[i][i + len] = true;
                }else if(s[i] == '(' || s[i] =='*')
                {
                    for(int j = i + 1;j <= i + len;j ++)
                    {
                        if((s[j] == ')' || s[j] == '*') 
                           && (j == i + 1 || dp[i + 1][j - 1]) 
                           && (j == i + len || dp[j + 1][i +len]))
                            dp[i][i + len] = true;
                    }
                }
            }
        }
        return dp[0][n - 1];
    }

算法3

(贪心) $O(n)$

我们使用两个标记low,high分别当前已经读入的字符中所有可能的情况中最少有多少个左括号，最多有多少个左括号。对于读入的字符c

• c = '('说明low = low + 1,high = high + 1
• c = ')'说明low = low - 1,high = high - 1
• c = '*'说明low = low - 1,high = high + 1这是因为，当前这个字符既可以看作是左括号也可以看作是右括号。

在匹配过程中，如果当前high < 0需要返回false。如果当前low < 0需要把low重置为0，这是因为不可以在已经不合法的序列中继续添加左括号。

最后只需要判断一下，low= 0说明完全匹配。时间复杂度$O(N)$。

    bool checkValidString(string s) {
        int low = 0 ,high = 0,n = s.length();
        for(int i = 0 ; i < n ; i ++)
        {
            if(s[i] == '('){low ++;high ++;}
            else if(s[i] ==')'){low --;high --;}
            else {low --;high ++;}
            if(high < 0) break;
            low = max(0,low);
        }
        return low == 0;
    }