题解 | #合法的括号字符串#

用dp[i][j] 表示 以 i 开始， j结尾的字符串s[i][j]是否为合法的括号字符串
确定dp[i][j]是否合法有两种方式，只要满足其中一个就合法
1、s[i]为左括号或者星号 s[j]为有括号或者星号,那么dp[i][j]完全依赖于的dp[i+1][j-1]的合法性
2、在[i,j]之间存在一个k，使得dp[i][k] 和 dp[k+1][j] 都是合法的，那么dp[i][j]合法（字符串需要长度大于等于3）

确定完转移方程之后，确定初始状态，当字符串长度只有1的时候，只有星号才是合法的
当字符串长度只有2的时候，只有当s[i]为左括号或者星号，s[j]为有括号或者星号的时候合法

最后答案就是dp[0][len-1]，len表示字符串长度。


这里需要注意当前求解的状态 和 前一个状态的依赖关系，决定了dp表达的填充顺序

#include<stdbool.h>
bool isValidString(char* s ) 
{
    // write code here
    if( s == NULL ) return false;
     
    int len = strlen( s );
    
    int dp[len][len];
    memset( dp , false, sizeof(dp));
    
    for( int i = 0; i <len ;++i )                //填充字符串只有一个字符情况下的dp表
    {
        if( *( s+i ) == '*' ) dp[i][i] = true;
    }
    
    for( int i = 0; i < len-1; ++i )            //填充字符串只有两个字符情况下的dp表
    {
        if( ( *( s+i ) == '(' || *( s+i ) == '*' )  && ( *( s+i+1 ) == ')' || *( s+i+1 ) == '*' ) ) dp[i][i+1] = true;
    }
    

    //注意填充顺序，因为dp[i][j]依赖于dp[i+1][j-1]的状态，如果i顺序填充的话，此时依赖的dp[i+1][j-1]还没有求解过，所以是无法正确计算的
    //所以需要i逆序填充，此时dp[i+1][j-1]是之前求解过得
    for( int i = len -3; i >= 0; --i )
    {
        for( int j = i+2; j < len; ++j )
        {
            if( ( *( s+i ) == '(' || *( s+i ) == '*' )  && ( *( s+j ) == ')' || *( s+j ) == '*' ) )
            {
                dp[i][j] = dp[i+1][j-1];
            }
            for( int k = i; k < j && dp[i][j] == false; ++k )
            {
                dp[i][j] = dp[i][k] && dp[k+1][j];
            }
        }
    }
    
    return dp[0][len-1];
}