LeetCode 678: Valid Parenthesis String Solution in Python – A Step-by-Step Guide

Imagine you’re a parenthesis detective handed a string like "()" or "()", where some characters are wildcards () that can magically become (, ), or nothing at all, and your job is to decide if it can form a valid parenthesis sequence—like "()" or "()" again. That’s the puzzle of LeetCode 678: Valid Parenthesis String, a medium-level problem that’s all about checking if a string with wildcards can balance its parentheses. Using Python, we’ll explore two solutions: the Best Solution, a greedy approach with range tracking for efficiency, and an Alternative Solution, a stack-based method with wildcard tracking that’s more intuitive but less optimized. With detailed examples, beginner-friendly breakdowns—especially for the greedy method—and clear code, this guide will help you crack that case, whether you’re new to coding or leveling up. Let’s dive into that string and start detecting!

What Is LeetCode 678: Valid Parenthesis String?

In LeetCode 678: Valid Parenthesis String, you’re given a string s containing (, ), and , where can represent either (, ), or an empty string. Your task is to determine if there exists at least one way to interpret the wildcards to make the string a valid parenthesis sequence—one where every ( has a matching ) and the balance (open count) never goes negative. Return True if possible, False otherwise. For example, with s = "()", can be ) to form "()" (valid), so return True. With s = "(()", no interpretation balances it, so return False. This problem tests your ability to handle flexible string validation efficiently.

Problem Statement

Input:

s: String of (, ), and *.

Output: A boolean—True if valid interpretation exists, False otherwise.
Rules:

* can be (, ), or empty.
Valid: Every ( matched by ), balance ≥ 0 at all points.
Check if any wildcard assignment works.

Constraints

1 ≤ s.length ≤ 100.
s[i] is (, ), or *.

Examples

Input: s = "()"

Output: True (Already valid)

Input: s = "(*)"

Output: True (* as ), forms "()")

Input: s = "(*))"

Output: True (* as (, forms "(())")

Input: s = "(()"

Output: False (No way to balance)

These examples set the string—let’s solve it!

Understanding the Problem: Validating with Wildcards

To solve LeetCode 678: Valid Parenthesis String in Python, we need to check if a string with (, ), and can be interpreted as a valid parenthesis sequence by assigning each as (, ), or empty. A brute-force approach—trying all possible wildcard combinations—would be O(3^n) (n = wildcards), impractical for s.length ≤ 100. Since we’re validating balance with flexibility, we can optimize using greedy range tracking or stack-based counting. We’ll use:

Best Solution (Greedy with Range Tracking): O(n) time, O(1) space—fast and elegant.
Alternative Solution (Stack with Wildcard Tracking): O(n) time, O(n) space—intuitive but more space-intensive.

Let’s start with the greedy solution, breaking it down for beginners.

Best Solution: Greedy with Range Tracking

Why This Is the Best Solution

The greedy with range tracking approach is the top choice for LeetCode 678 because it’s highly efficient—O(n) time with O(1) space—and uses a brilliant insight: track the minimum and maximum possible open parenthesis counts as you scan the string, ensuring the balance stays valid. It fits constraints (s.length ≤ 100) perfectly and is intuitive once you see the range logic. It’s like juggling the lowest and highest possibilities to ensure a valid outcome!

How It Works

Think of this as a balance juggler:

Step 1: Initialize Range:

low: Minimum open count, starts at 0.
high: Maximum open count, starts at 0.

Step 2: Scan String:

For each char:

(: low += 1, high += 1 (must open).
): low = max(0, low - 1), high -= 1 (close if possible).
*: low = max(0, low - 1), high += 1 (close or open).

If high < 0 at any point, return False (too many closes).

Step 3: Check Final Balance:

Return True if low = 0 (min balance achievable), False otherwise.

Step 4: Return Result:

Return validity check.

It’s like a range checker—track and balance!

Step-by-Step Example

Example: s = "(*)"

Step 1: low = 0, high = 0.
Step 2: Scan:

(: low = 1, high = 1.
*: low = max(0, 1-1) = 0, high = 1+1 = 2.
): low = max(0, 0-1) = 0, high = 2-1 = 1.

Step 3: low = 0, high ≥ 0, return True.
Output: True (* as ) forms "()").

Example: s = "(()"

Step 1: low = 0, high = 0.
Step 2: Scan:

(: low = 1, high = 1.
(: low = 2, high = 2.
): low = max(0, 2-1) = 1, high = 2-1 = 1.

Step 3: low = 1 ≠ 0, return False.
Output: False (Unbalanced).

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

class Solution:
    def checkValidString(self, s: str) -> bool:
        # Step 1: Initialize min and max open counts
        low = 0  # Min open parentheses
        high = 0  # Max open parentheses

        # Step 2: Scan string and update range
        for char in s:
            if char == '(':
                low += 1
                high += 1
            elif char == ')':
                low = max(0, low - 1)
                high -= 1
            else:  # '*'
                low = max(0, low - 1)  # Treat as ')'
                high += 1              # Treat as '('

            # If high < 0, too many closes even with max flexibility
            if high < 0:
                return False

        # Step 3: Check if min balance is zero
        return low == 0

Lines 4-6: Init: low and high start at 0.
Lines 9-21: Scan:

(: Increment both.
): Decrement high, low only if positive.
*: Decrement low (if positive), increment high.
Check high < 0 for early exit.

Line 24: Return: True if low = 0 (balance possible).
Time Complexity: O(n)—single pass.
Space Complexity: O(1)—two variables.

This is like a parenthesis balancer—range and check!

Alternative Solution: Stack with Wildcard Tracking

Why an Alternative Approach?

The stack with wildcard tracking approach uses stacks—O(n) time, O(n) space. It’s more intuitive, tracking open parentheses and wildcards separately, then matching them, but uses more space and complexity. It’s like keeping a ledger of possibilities and balancing them at the end!

How It Works

Picture this as a stack matcher:

Step 1: Use two stacks:

open_stack: Indices of unmatched (.
star_stack: Indices of *.

Step 2: Process string:

(: Push index to open_stack.
): Pop from open_stack or star_stack (as (), fail if both empty.
*: Push index to star_stack.

Step 3: Match remaining:

Pop open_stack and star_stack pairs (star as )), ensure stars are after opens.

Step 4: Return True if all matched (open_stack empty).

It’s like a stack balancer—track and pair!

Step-by-Step Example

Example: s = "(*)"

Step 1: open_stack = [], star_stack = [].
Step 2: Process:

( (0): open_stack = [0].
* (1): star_stack = [1].
) (2): Pop open_stack, open_stack = [], no need for star.

Step 3: open_stack empty, ignore star_stack[1] (can be empty).
Step 4: Return True.
Output: True.

Example: s = "(()"

Step 1: Init stacks empty.
Step 2: Process:

( (0): open_stack = [0].
( (1): open_stack = [0, 1].
) (2): Pop open_stack, open_stack = [0].

Step 3: open_stack = [0], star_stack = [], no stars to match.
Step 4: Return False.
Output: False.

Code for Stack Approach

class Solution:
    def checkValidString(self, s: str) -> bool:
        # Step 1: Initialize stacks
        open_stack = []  # Indices of unmatched '('
        star_stack = []  # Indices of '*'

        # Step 2: Process string
        for i, char in enumerate(s):
            if char == '(':
                open_stack.append(i)
            elif char == ')':
                if open_stack:
                    open_stack.pop()
                elif star_stack:
                    star_stack.pop()
                else:
                    return False
            else:  # '*'
                star_stack.append(i)

        # Step 3: Match remaining opens with stars
        while open_stack and star_stack:
            if open_stack[-1] > star_stack[-1]:  # Star must be after open
                return False
            open_stack.pop()
            star_stack.pop()

        # Step 4: Return True if all opens matched
        return len(open_stack) == 0

Lines 4-6: Init: Empty stacks for opens and stars.
Lines 9-19: Process:

Push ( to open_stack, pop for ), push * to star_stack.

Lines 22-27: Match:

Pair opens with stars, check order.

Line 30: Return: True if all opens matched.
Time Complexity: O(n)—single pass.
Space Complexity: O(n)—stack sizes.

It’s a stack pairer—track and balance!

Comparing the Two Solutions

Greedy (Best):

Pros: O(n) time, O(1) space, fast and minimal.
Cons: Range logic less obvious.

Stack (Alternative):

Pros: O(n) time, O(n) space, intuitive stacking.
Cons: More space, slightly more complex.

Greedy wins for efficiency.

Additional Examples and Edge Cases

Input: s = ""

Output: True.

Input: s = "*)"

Output: False (No opening to match).

Greedy handles these well.

Complexity Breakdown

Greedy: Time O(n), Space O(1).
Stack: Time O(n), Space O(n).

Greedy is optimal.

Key Takeaways

Greedy: Range juggling—smart!
Stack: Wildcard stacking—clear!
Parentheses: Balancing is fun.
Python Tip: Greedy rocks—see Python Basics.

Final Thoughts: Crack That Case

LeetCode 678: Valid Parenthesis String in Python is a fun validation challenge. Greedy with range tracking offers speed and elegance, while stack-based tracking provides a clear alternative. Want more? Try LeetCode 20: Valid Parentheses or LeetCode 32: Longest Valid Parentheses. Ready to detect? Head to Solve LeetCode 678 on LeetCode and validate that string today!