Leetcode 678 :- Valid Parenthesis String

#leetcode #algorithms #datastructures #recursion

Today I solved the question LC 678 Valid Parenthesis String

Intuition

Since we have 3 choices to make for when we encounter a * we can solve this recursively.

Approach

Since the recursive solution would lead to a TLE for when s="**********************" therefore we can optimize the recursive calls using Dynamic Programming

Complexity

Time complexity: For the recursive code :- At the worst possible scenario we are making 3 branches when we encounter an * so the TC is 3^n

Code

//👇👇 Recursive Code
 var checkValidString = function (s, index = 0, count = 0) {
     if (count < 0) return false
     if (index === s.length) {
         return count === 0
     }
     if (s[index] === '(') {
         return checkValidString(s, index + 1, count + 1)
     } else if (s[index] === ')') {
         return checkValidString(s, index + 1, count - 1)
     } else {
         return checkValidString(s, index + 1, count + 1) || checkValidString(s, index + 1, count - 1) || checkValidString(s, index + 1, count)
     }
 };

// 👇👇DP Code
var checkValidString = function (s, index = 0, count = 0, memo = {}) {
    if (count < 0) return false;
    if (index === s.length) {
        return count === 0;
    }
    // Create a unique key for the current state
    const key = `${index},${count}`;
    if (key in memo) {
        return memo[key]; // Return cached result
    }
    let result;
    if (s[index] === '(') {
        result = checkValidString(s, index + 1, count + 1, memo);
    } else if (s[index] === ')') {
        result = checkValidString(s, index + 1, count - 1, memo);
    } else { // s[index] === '*'
        result = checkValidString(s, index + 1, count + 1, memo) || // Treat '*' as '('
                 checkValidString(s, index + 1, count - 1, memo) || // Treat '*' as ')'
                 checkValidString(s, index + 1, count, memo);       // Treat '*' as empty
    }
    memo[key] = result; // Store the result in the cache
    return result;
};