#678

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Valid Parenthesis String

Solve the Valid Parenthesis String problem by leveraging state transition dynamic programming to handle parentheses and wildcard '*' characters.

string dynamic programming stack greedy

Problem Statement

Given a string s consisting of three types of characters: '(', ')', and '', determine if the string is valid. A valid string is one where every open parenthesis has a corresponding close parenthesis, and ' ' can act as a parenthesis or be ignored.

The rules for a valid string are as follows: the '' can represent either a '(', a ')', or be an empty string. The string is valid if, after replacing ' ' in any possible way, the result is a properly balanced parentheses string.

Examples

Example 1

Input: s = "()"

Output: true

Example details omitted.

Example 2

Input: s = "(*)"

Output: true

Example details omitted.

Example 3

Input: s = "(*))"

Output: true

Example details omitted.

Constraints

1 <= s.length <= 100
s[i] is '(', ')' or '*'.

Solution Approach

State Transition Dynamic Programming

Use dynamic programming to track all valid states during the iteration of the string. At each step, consider how the previous states can transition based on the current character, whether it is '(', ')', or '*'.

Backtracking for Wildcard Handling

Backtrack to explore every possible way the '*' character can be replaced. Consider its three possibilities: '(', ')', or an empty string, and verify if any leads to a valid parentheses string.

Greedy Approach for Parenthesis Matching

While iterating through the string, attempt a greedy approach by matching parentheses as they appear. If the balance of open and close parentheses is maintained, the string can be considered valid.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The time complexity of the solution is O(n) due to the need to iterate through the string once. The space complexity is O(1) as we only need a constant amount of space to store the current state information.

What Interviewers Usually Probe

Assess the candidate’s understanding of dynamic programming, especially in relation to state transitions.
Evaluate how well the candidate uses backtracking to explore multiple combinations of wildcard substitutions.
Look for the candidate's ability to optimize their approach, ensuring they don't exceed O(n) time complexity.

Common Pitfalls or Variants

Common pitfalls

Failing to account for the wildcard '*' and treating it as a fixed character can lead to incorrect solutions.
Not properly handling all possible states of the string during backtracking, leading to missed valid configurations.
Overcomplicating the solution by not leveraging efficient state transitions in dynamic programming.

Follow-up variants

Modify the problem to disallow the use of the wildcard '*' character.
Implement the solution in a way that restricts the length of valid parentheses subsequences.
Consider the problem with additional constraints such as limiting the number of wildcards or parentheses.

FAQ

How do you solve the Valid Parenthesis String problem using dynamic programming?

By keeping track of possible valid states as you iterate through the string, considering how each character affects the balance of parentheses and utilizing dynamic transitions.

What is the role of the wildcard '*' in the Valid Parenthesis String problem?

The wildcard '*' can represent either '(', ')', or be ignored. The solution must explore all three possibilities during the evaluation.

How can backtracking be used in this problem?

Backtracking explores all possible ways the '*' can be substituted to verify if any combination results in a valid parentheses string.

What are some common pitfalls in solving the Valid Parenthesis String problem?

Failing to handle the wildcard properly, missing potential valid configurations during backtracking, or overcomplicating the solution by not using state transitions efficiently.

What is the time complexity of solving the Valid Parenthesis String problem?

The time complexity is O(n), where n is the length of the string, as we only need to iterate through the string once.

terminal

Solution

Solution 1: Dynamic Programming

Let `dp[i][j]` be true if and only if the interval `s[i], s[i+1], ..., s[j]` can be made valid. Then `dp[i][j]` is true only if:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def checkValidString(self, s: str) -> bool:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        for i, c in enumerate(s):
            dp[i][i] = c == '*'
        for i in range(n - 2, -1, -1):
            for j in range(i + 1, n):
                dp[i][j] = (
                    s[i] in '(*' and s[j] in '*)' and (i + 1 == j or dp[i + 1][j - 1])
                )
                dp[i][j] = dp[i][j] or any(
                    dp[i][k] and dp[k + 1][j] for k in range(i, j)
                )
        return dp[0][-1]

Solution 2: Greedy

Scan twice, first from left to right to make sure that each of the closing brackets is matched successfully, and second from right to left to make sure that each of the opening brackets is matched successfully.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def checkValidString(self, s: str) -> bool:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        for i, c in enumerate(s):
            dp[i][i] = c == '*'
        for i in range(n - 2, -1, -1):
            for j in range(i + 1, n):
                dp[i][j] = (
                    s[i] in '(*' and s[j] in '*)' and (i + 1 == j or dp[i + 1][j - 1])
                )
                dp[i][j] = dp[i][j] or any(
                    dp[i][k] and dp[k + 1][j] for k in range(i, j)
                )
        return dp[0][-1]

Continue Practicing

#488 zuma game #402 remove k digits #316 remove duplicate letters