public class Solution {
    static bool[,] memo;
    public bool CheckValidString(string s) {
        memo = new bool[s.Length, s.Length];
        return Solve(s, 0, 0);
    }

    public bool Solve(string s, int i, int balance){
        if(i == s.Length){
            return balance == 0;
        }

        if(memo[i, balance]) return memo[i, balance];

        if(s[i] == '(') memo[i, balance] = Solve(s, i + 1, balance + 1);
        else if(s[i] == ')') {
            if(balance <= 0) memo[i, balance] = false;
            else memo[i, balance] = Solve(s, i + 1, balance - 1);
        }
        else memo[i, balance] = Solve(s, i + 1, balance) || Solve(s, i + 1, balance + 1) || (balance != 0 &&Solve(s, i + 1, balance - 1));

        return memo[i, balance];
    }
}