Solution Explanation for Valid Parenthesis String

This problem asks whether a given string containing '(', ')', and '*' characters is valid. A valid string adheres to these rules:

1. Every '(' must have a matching ')'.
2. Every ')' must have a matching '('.
3. '(' must come before its matching ')'.
4. '*' can act as '(', ')', or an empty string.

Two approaches are presented: dynamic programming and a greedy approach.

Solution 1: Dynamic Programming

This approach uses a dynamic programming table dp[i][j] to store whether the substring s[i...j] is valid. The base cases are single characters: a '*' is valid, while '(' and ')' are not.

The recursive relation is built as follows:

• dp[i][j] = True if:
  • s[i] is '*' and s[i+1...j] is valid (dp[i+1][j]).
  • s[i] can be treated as '(' and s[j] as ')', and the inner substring is valid (s[i+1...j-1] is valid and dp[i+1][j-1]).
  • There exists a k between i and j such that s[i...k] and s[k+1...j] are both valid. This represents splitting the substring into two valid parts.

The algorithm iterates through substrings of increasing length, using previously computed results. dp[0][n-1] (where n is the string length) finally indicates whether the entire string is valid.

Time Complexity: O(n^3) due to the three nested loops (the outer two for substring selection and the inner one to find the splitting point k). Space Complexity: O(n^2) for the dynamic programming table.

Solution 2: Greedy Approach

This more efficient solution uses two scans of the string:

First Scan (Left to Right): It maintains a counter x. For each character:

• If it's '(' or '*', increment x.
• If it's ')' and x is positive (a matching '(' or '*' exists), decrement x.
• If it's ')' and x is 0, the string is invalid (unmatched ')').

Second Scan (Right to Left): It resets x and performs a similar scan in reverse.

• If it's ')' or '*', increment x.
• If it's '(' and x is positive, decrement x.
• If it's '(' and x is 0, the string is invalid (unmatched '(').

If both scans complete without finding invalid conditions, the string is valid.

Time Complexity: O(n) because it iterates through the string twice. Space Complexity: O(1) because only a constant amount of extra space is used.

Code Examples (Python)

Solution 1 (Dynamic Programming):

def checkValidString(s: str) -> bool:
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = s[i] == '*'
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if (s[i] in '(*' and s[j] in '*)' and (length == 2 or dp[i + 1][j - 1])):
                dp[i][j] = True
            else:
                for k in range(i, j):
                    if dp[i][k] and dp[k + 1][j]:
                        dp[i][j] = True
                        break
    return dp[0][n - 1]
 

Solution 2 (Greedy):

def checkValidString(s: str) -> bool:
    x = 0
    for c in s:
        if c in '(*':
            x += 1
        elif x > 0:
            x -= 1
        else:
            return False
    x = 0
    for c in reversed(s):
        if c in '*)':
            x += 1
        elif x > 0:
            x -= 1
        else:
            return False
    return True

The greedy approach is significantly more efficient for this problem, making it preferable in terms of both time and space complexity. The dynamic programming solution is included for completeness and to demonstrate a different algorithmic approach. Code in other languages (Java, C++, Go) would follow similar logic with appropriate syntax changes.