checkValidString = function(s) {
    const isBaseCase = s.length === 0;
    if (isBaseCase) return true;

    const dp = new Array(s.length).fill()
        .map(() => new Array(s.length).fill(false));

    for (let i = 0; i < s.length; i++) {/* Time O(N) */
        if (isStar(s[i])) dp[i][i] = true;
        
        const isInBound = i < (s.length - 1)
        const isOpenedOrStar = isOpened(s[i]) || isStar(s[i])
        const isClosedOrStar = isClosed(s[i + 1]) || isStar(s[i + 1])
        
        const isValid = isInBound && isOpenedOrStar && isClosedOrStar
        if (isValid) dp[i][i + 1] = true;/* Space O(N^2) */
    }

    for (let size = 2; size < s.length; size++) {/* Time O() */
        for (let i = 0; i + size < s.length; i++) {/* Time O(N) */
            const isStarOrDP = isStar(s[i]) && isDP(dp, (i + 1), (i + size))
            if (isStarOrDP) { dp[i][i + size] = true; continue; }
        
            const isOpenedOrStar = isOpened(s[i]) || isStar(s[i])
            if (isOpenedOrStar) check(dp, size, i); /* Time O(N) */
        }
    }
    
    return dp[0][s.length - 1];
}
https://leetcode.com/problems/valid-parenthesis-string/
Time O(N^3) | Space O(N^2)
@param {string} s
@return {boolean}