Valid Parenthesis String - Leetcode Solution

The Valid Parenthesis String problem on LeetCode is a problem in which one has to determine whether a given string of parentheses is valid or not. The string is considered valid if each open bracket has a corresponding closing bracket and the brackets are properly nested.

Here is a detailed solution to the problem:

Approach 1: Using a stack and backtracking

One way to check if a given string of parentheses is valid is to use a stack. Whenever we encounter an opening bracket, we push it onto the stack. Whenever we encounter a closing bracket, we pop an opening bracket from the stack. If the stack is empty at the end of the string, then the string is valid. Here is the pseudocode for this approach:

1. Create an empty stack.
2. Iterate through each character in the string: a. If the character is an opening bracket, push it onto the stack. b. If the character is a closing bracket, pop an opening bracket from the stack. c. If the stack is empty, the string is invalid. Return false.
3. If the stack is not empty, the string is invalid. Return false.
4. If the stack is empty, the string is valid. Return true.

One problem with this approach is that it doesn't handle wildcard characters ('*'). A wildcard character can be either an opening, closing, or empty bracket. To handle wildcard characters, we need to use backtracking. We try every possible combination of brackets and check if any of them result in a valid string. Here is the pseudocode for the backtracking approach:

1. Define a recursive function checkValid(index, openCount, closeCount): a. If index == n (the length of the string): i. If openCount == closeCount, return true. ii. Otherwise, return false. b. If the character at index is '(', call checkValid(index+1,openCount+1,closeCount). c. If the character at index is ')': i. If openCount > closeCount, call checkValid(index+1,openCount,closeCount+1). ii. If openCount < closeCount, return false. iii. If openCount == closeCount, try both options (call checkValid(index+1,openCount+1,closeCount) and checkValid(index+1,openCount,closeCount+1)). d. If the character at index is '*', try all three options (opening, closing, or empty bracket) and call checkValid in each case.
2. Call the checkValid function with initial values (0,0,0).

The time complexity of this approach is exponential because we check every possible combination of brackets. The space complexity is O(n) because of the recursive function call stack.

Approach 2: Greedy approach

A better approach to solve this problem is to use a greedy approach. We keep track of the minimum and maximum possible number of opening brackets needed to balance the remaining string of brackets at each index. If at any step, the number of closing brackets exceeds the maximum number of opening brackets, the string is invalid. If at the end of the string, the number of opening brackets is less than the minimum possible number of opening brackets, the string is invalid. Otherwise, the string is valid. Here is the pseudocode for this approach:

1. Initialize two variables: minOpenCount = 0 (minimum possible number of opening brackets needed), maxOpenCount = 0 (maximum possible number of opening brackets needed).
2. Iterate through each character in the string: a. If the character is '(', increment both minOpenCount and maxOpenCount. b. If the character is ')', decrement both minOpenCount and maxOpenCount. c. If the character is '*', try all three options (opening, closing, or empty bracket) and update minOpenCount and maxOpenCount accordingly: i. If we use a closing bracket, decrement both minOpenCount and maxOpenCount. ii. If we use an opening bracket, increment both minOpenCount and maxOpenCount. iii. If we use an empty bracket, decrement minOpenCount and increment maxOpenCount. d. If maxOpenCount becomes negative, the string is invalid. Return false. e. At the end of the string, if minOpenCount is not zero, the string is invalid. Otherwise, the string is valid. Return true.

The time complexity of this approach is O(n) because we iterate through the string only once. The space complexity is O(1) because we use only two variables to keep track of the minimum and maximum possible number of opening brackets.

1